Language recongized by a “quasi realtime register machine”?

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:

1. Consuming transition, in which action is determined by the next input letter, which is consumed by this transition.
2. 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.

• One-counter automata are by definition a restricted kind of PDA and thus recognize (a strict subset of) context-free languages. Which claim of Fisher are you referring to? – Patrick Totzke Aug 5 at 16:06
• Fisher gives an example of a non-CFL accepted by a non-deterministic one counter machine: – Yossi Gil Aug 6 at 7:21
• I think you are misreading the Fisher paper you cite above: The only related claim I can see is point (6) in Thm. 3, page 375. But there he compares languages which are domains of deterministic Pushdown transducers ($\mathcal{P}$) with domains of nondet. one-counter transducers ($\mathcal{C}'$) (p374, top). These classes are strictly more general than CfL and one-counter languages (defined by acceptors)! – Patrick Totzke Aug 6 at 8:39
• Indeed, the little difference between transducers and acceptors – Yossi Gil Aug 11 at 11:26