<p>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.</p>

<p>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. </p>

<p>More precisely a QRRM is similar to a pushdown automaton (PDA). Like a PDA, a QRRM has a finite set of <em>internal states</em> <span class="math-container">$Q$</span>, an <em>initial state</em> <span class="math-container">$q_0\in Q$</span>, and a set of <em>accepting states</em> <span class="math-container">$F\subseteq Q$</span>.
A PDA uses a pushdown (stack) as <em>auxiliary storage</em>---A QRRM uses instead a finite number of integer registers. Like a PDA, a QRRM has two kinds of transitions:</p>

<ol>
<li><strong>Consuming transition</strong>, in which action is determined by the next input letter, which is consumed by this transition.</li>
<li><strong>Eplsion transition</strong> (<span class="math-container">$\epsilon$</span>-transition), in which action does not depend on the input, and no input letter is consumed.</li>
</ol>

<p>Both kinds of transitions depend on the current state <span class="math-container">$q\in Q$</span> and on the value of the auxiliary storage. In a consuming transition, the dependency is also on the next input letter <span class="math-container">$\sigma\in\Sigma$</span>. Quasi-realtime means that there is a constant that bounds from above the number of <span class="math-container">$\epsilon$</span>-transitions that follow a consuming transition.</p>

<p>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. </p>

<p>In both kinds of transitions, the automaton may change its internal state from a state <span class="math-container">$q\in Q$</span> to a state <span class="math-container">$q'\in Q$</span> 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 <span class="math-container">$i$</span>, by setting <span class="math-container">$r_i \leftarrow r_i + r_j$</span> or <span class="math-container">$r_i \leftarrow r_i- r_j$</span>.</p>

<p>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 <span class="math-container">$a^nb^nc^n$</span>. 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 <a href="https://cstheory.stackexchange.com/questions/18591/has-a-result-of-book-and-greibach-on-quasi-realtime-languages-been-improved">Book and Greibach</a>?</p>

<hr>

<p>A related problem is that of a one-counter machine, which can recognize non CFL languages. Checking out the example in <a href="https://core.ac.uk/download/pdf/82706076.pdf" rel="nofollow noreferrer">Patrick C.Fischer (66)</a>, we see that it can be done in quasi-realtime.</p>

CC BY-SA 4.0
2019-08-05T16:06:08.770Z
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
CC BY-SA 4.0
2019-08-06T07:21:23.610Z
Fisher gives an example of a non-CFL accepted by a non-deterministic one counter machine:
Yossi Gil
CC BY-SA 4.0
2019-08-06T08:39:29.800Z
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
CC BY-SA 4.0
2019-08-11T11:26:08.460Z
Indeed, the little difference between transducers and acceptors
Yossi Gil
<automata-theory><counter-automata>
Language recongized by a "quasi realtime register machine"?
Yossi Gil
# Language recongized by a "quasi realtime register machine"?

(Asked by: username_0 on 2019-08-03)

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](https://cstheory.stackexchange.com/questions/18591/has-a-result-of-book-and-greibach-on-quasi-realtime-languages-been-improved)?

---

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)](https://core.ac.uk/download/pdf/82706076.pdf), we see that it can be done in quasi-realtime.

**Tags:** automata-theory, counter-automata
> **Comments:**
> **username_1**: 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?  
> **username_0**: Fisher gives an example of a non-CFL accepted by a non-deterministic one counter machine:  
> **username_1**: 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)!  
> **username_0**: Indeed, the little difference between transducers and acceptors  

---

## 0 answers

