Stateless multicounter 5??3? WatsonCrick automata: the deterministic case
We consider stateless counter machines which mix the features of one-head counter machines and special two-head WatsonCrick automata (WK-automata). These biologically motivated machines have heads that read the input starting from the two extremes. The reading process is finished when the heads meet. The machine is realtime or non-realtime depending on whether the heads are required to advance at each move. A counter machine is k -reversal if each counter makes at most k alternations between increasing mode and decreasing mode on any computation, and reversal bounded if it is k-reversal for some k. In this paper we concentrate on the properties of deterministic stateless realtime WK-automata with counters that are reversal bounded. We give examples and establish hierarchies with respect to counters and reversals.
watsoncrick automata counter machine dna computing membrane computing reversal bounded machine stateless machine universality