7
$\begingroup$

Quasi-realtime languages are defined as languages accepted by nondeterministic multitape Turing machines in quasi-real time. Ronald Book and Sheila Greibach have shown in their 1970 paper that every quasi-realtime language can be accepted by a nondeterministic automaton having one stack and one pushdown store. However, at the time it was open if a nondeterministic automaton with two pushdown stores suffices.

Since the mentioned paper is quite old and seems to have received significant attention (at least I deduce so from the number of citations), I would like to ask if there has been any progress on the above mentioned problem. In particular, has anybody proved that two pushdown stores are sufficient/insufficient? Or has anybody improved the result in some other way?

Improve this question
$\endgroup$
3
  • $\begingroup$ What is "quasi-realtime"? $\endgroup$
    – Joshua Grochow
    Aug 12 '13 at 15:20
  • 1
    $\begingroup$ Quasi-realtime means bounded delay, i.e. any configuration of the machine that is reachable from another is reachable in a bounded number of steps. Book and Greibach show that for any linear time NDTM there is a quasi-realtime machine that accepts the same language, so this type of restriction is not usually important except for the edge cases. The OP really seems to be asking: is every linear time (NDTM) language accepted by a nondeterministic automaton with two pushdown stores and bounded delay? $\endgroup$
    – András Salamon
    Aug 15 '13 at 10:06
  • $\begingroup$ @JoshuaGrochow Sorry for a late response, I have been out of network connection for a time. András Salamon is essentially right, but his first sentence needs some clarification: it is not true that any reachable configuration has to be reachable in a bounded number of steps. This is true only for configurations reachable without reading any input. In other words, beginning in any configuration, the number of steps that can be executed without reading any input is bounded by some constant independent of the configuration. $\endgroup$
    – 042
    Aug 18 '13 at 11:47

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.