Ronald Book
ABSTRACT
The purpose of this paper is to establish the following result.
Theorem 3.1. Let L be a language. The following are equivalent:
(i) L is accepted by a nondeterministic multipushdown acceptor which operates in such a way that in every accepting computation each pushdown store makes at most a bounded number of reversals and which runs in linear time;
(ii) L is accepted by a nondeterministic multipushdown acceptor which operates in such a way that in every accepting computation each pushdown store makes at most one reversal and which runs in real time;
(iii) L is the length-preservlng homomorphie image of the intersection of some finite number of linear context-free languages;
(iv) L is accepted by a nondeterministlc acceptro with three pushdown stores which operates in such a way that in every computation each pushdown store makes at most one reversal and which rmls in real time;
(v) L is the length-preservlng homomorphic image of the intersection of three linear context-free languages.
- 1.S. Aanderaa, On k-tape versus (k+l)-tape realtime computation, to appear.Google Scholar
- 2.B. Baker and R. Book, Reversal-bounded multipushdown machines, Journal of Computer and System Sciences, to appear. Google ScholarDigital Library
- 3.R. Book and S. Greibach, Quasi-realtime languages, Math. Systems Theory 4 (1970), 97-111.Google ScholarCross Ref
- 4.S. Ginsburg and E. Spanier, Finite-turn pushdown automata, SIAM Journal of Control. 4 (1966), 429-453.Google Scholar
- 5.S. Greibach and S. Ginsburg, Multi-tape AFA, JACM 19 (1972), 192-221. Google ScholarDigital Library
- 6.S. Greibach and J. Hopcroft, Scattered context grammars, Journal of Computer and Systems Science 3 (1969), 233-247.Google ScholarDigital Library
- 7.J. Hartmanis, Tape-reversal bounded Turing machine computations, Journal of Computer and System Sciences 2 (1968), 117-135.Google ScholarDigital Library
- 8.J. Hartmanis and R. Stearns, On the computational complexity of algorithms, Trans. American Math. Society 117 (1965), 285-306.Google Scholar
- 9.L. Liu and P. Weiner, An infinite hierarchy of intersections of context-free languages, Math. Systems Theory 7 (1973), 185-192.Google ScholarCross Ref
- 10.M. Rabin, Real-time computation, Israel Journal of Mathematics 1 (1963), 203-211.Google ScholarCross Ref
Index Terms
- Intersections of linear context-free languages and reversal-bounded multipushdown machines (Extended Abstract)
Recommendations
Reversal-bounded multipushdown machines
Several representations of the recursively enumerable (r.e.) sets are presented. The first states that every r.e. set is the homomorphic image of the intersection of two linear context-free languages. The second states that every r.e. set is accepted by ...
Reversal-Bounded Acceptors and Intersections of Linear Languages
A Turing machine whose behavior is restricted so that each read-write head can change its direction only a bounded number of times is reversal-bounded. Here we consider nondeterministic multitape acceptors which are both reversal-bounded and also operate ...
Comments