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?
Has a result of Book and Greibach on Quasi-Realtime languages been improved?
reference request;fl.formal languages;automata theory