0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Patrick Totzke Aug 5 at 16:06
  • $\begingroup$ Fisher gives an example of a non-CFL accepted by a non-deterministic one counter machine: $\endgroup$ – Yossi Gil Aug 6 at 7:21
  • 1
    $\begingroup$ 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)! $\endgroup$ – Patrick Totzke Aug 6 at 8:39
  • $\begingroup$ Indeed, the little difference between transducers and acceptors $\endgroup$ – Yossi Gil Aug 11 at 11:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.