<p>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 <a href="http://link.springer.com/article/10.1007/BF01705890" rel="noreferrer">1970 paper</a> 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.</p>

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

CC BY-SA 3.0
2013-08-12T15:20:24.573Z
What is "quasi-realtime"?
Joshua Grochow
CC BY-SA 3.0
2013-08-15T10:06:07.633Z
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?_
András Salamon
CC BY-SA 3.0
2013-08-18T11:47:56.207Z
@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.
042
<reference-request><fl.formal-languages><automata-theory>
Has a result of Book and Greibach on Quasi-Realtime languages been improved?
042
# Has a result of Book and Greibach on Quasi-Realtime languages been improved?

(Asked by: username_0 on 2013-08-09)

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](http://link.springer.com/article/10.1007/BF01705890) 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?

**Tags:** reference-request, fl.formal-languages, automata-theory

> **Comments:**
> **username_1**: What is "quasi-realtime"?  
> **username_2**: 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?_  
> **username_0**: @JoshuaGrochow Sorry for a late response, I have been out of network connection for a time. username_2 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.  

---

## 0 answers

