Counter machines are very powerful. Even two counters suffice for making these Turing complete. But, in simulating a Turing machine the counter machine encodes in its integers a large amount of data. The encoding requires quite some time to process.
What if we restrict the counter machines to reasonably sized integers, and to a reasonable amount of time? Restricting the counter machine to increments and decrements limits the computation to unary representation, so allow addition and subtraction of registers. Restricting time is to a constant amount of work for each input letter, what is called quasi-realtime. Let quasi-realtime register machine (QRRM) be a machine that does a constant amount of work on each input letter and allowed additions and substractions of integer registers and may take action based on comparing these registers to zero.
More precisely a QRRM is similar to a pushdown automaton (PDA). Like a PDA, a QRRM has a finite set of internal states $Q$, an initial state $q_0\in Q$, and a set of accepting states $F\subseteq Q$. A PDA uses a pushdown (stack) as auxiliary storage---A QRRM uses instead a finite number of integer registers. Like a PDA, a QRRM has two kinds of transitions:
- Consuming transition, in which action is determined by the next input letter, which is consumed by this transition.
- Eplsion transition ($\epsilon$-transition), in which action does not depend on the input, and no input letter is consumed.
Both kinds of transitions depend on the current state $q\in Q$ and on the value of the auxiliary storage. In a consuming transition, the dependency is also on the next input letter $\sigma\in\Sigma$. Quasi-realtime means that there is a constant that bounds from above the number of $\epsilon$-transitions that follow a consuming transition.
The dependency on auxiliary storage is by popping a symbol from a stack in a PDA. The dependency on auxiliary storage is by checking whether each of the registers is equal to zero.
In both kinds of transitions, the automaton may change its internal state from a state $q\in Q$ to a state $q'\in Q$ and update auxiliary storage. A QRRM updates it auxiliary storage by incrementing, decrementing, or clearing any of its registers. It is also allowed to change the value of some register $i$, by setting $r_i \leftarrow r_i + r_j$ or $r_i \leftarrow r_i- r_j$.
The question is with regard to the class of languages accepted by QRRM. It can clearly recognize languages such as expressions, and also context-sensitive languages such as $a^nb^nc^n$. Can a QRRM emulate a linear-bounded-automaton (LBA)? Any difference between the deterministic and the non-deterministic versions of the machine? How is this related to the result of Book and Greibach?
A related problem is that of a one-counter machine, which can recognize non CFL languages. Checking out the example in Patrick C.Fischer (66), we see that it can be done in quasi-realtime.