Counter machines are finite state automata equipped with a fixed, finite number of counters. The machine can check whether a counter is zero or not. In each step, a counter's value can be increased by one, decreased by one, or left unchanged. Counter machines with two counters are Turing universal [5]. 5' → 3' Watson-Crick automata are two-head finite automata whose reading heads start from the two opposite ends of the input in the beginning of the computation [3,4]. Stateless multicounter 5' → 3' Watson-Crick automata were defined in [1,2]. The following is a more general definition, allowing to read strings in a transition.
展开▼
