Relationships between pushdown automata with counters and complexity classes
Tóm tắt
In this paper a machine model is defined whose access to the storage cells is controlled by means of address registers. It is shown that every set acceptable by such a machine within time boundc⋅n
p,p ∈ ℕ, is accepted by a deterministic 2p-head two-way pushdown automaton which has additional counters of length log2
n. On the other hand every set acceptable by a deterministicp-head two-way pushdown automaton can be accepted by this machine model within time boundc⋅n
p⋅log2
n.
Tài liệu tham khảo
A. V. Aho, J. E. Hopcroft andJ. D. Ullman, Time and tape complexity of pushdown automaton languages,Information and Control 13 (1968), 186–206.
S. A. Cook, Characterizations of pushdown machines in terms of time-bounded computers,J. Assoc. Comput. Mach. 18 (1971), 4–18.
J. Earley, An efficient context-free parsing algorithm,C. Assoc. Comput. Mach. 13 (1970), 94–102.
J. N. Gray, M. A. Harrison andO. H. Ibarra, Two-way pushdown automata,Information and Control 10 (1967), 30–70.
M. A. Harrison andO. H. Ibarra, Multi-tape and multi-head pushdown automata,Information and Control 13 (1968), 433–470.
J. Hartmanis, P. M. Lewis andR. E. Stearns,Hierarchies of Memory Limited Computations, IEEE Conference Record 1965, 179–190.
J. Hartmanis andR. E. Stearns, On the computational complexity of algorithms,Trans. Amer. Math. Soc. 117 (1965), 285–306.
J. E. Hopcroft andJ. D. Ullman,Formal Languages and Their Relation to Automata, Addison-Wesley, Reading, Mass., 1969.
T. Kameda, Pushdown automata with counters,J. Computer and System Sciences 6 (1972), 138–150.
T. Kasami, A note on computing time for recognition of languages generated by linear grammars,Information and Control 10 (1967), 209–214.
T. Kasami andT. Torii, A syntax-analysis procedure for unambiguous context-free grammars,J. Assoc. Comput. Mach. 16 (1969), 423–431.
B. Monien,Beziehungen zwischen Zeitkomplexitätsklassen und Kellerautomaten mit Zählern, Berichte Inst. f. Informatik d. Universität Hamburg 71/1.
D. H. Younger, Recognition and parsing of context-free languages in timen 3,Information and Control 10 (1967), 189–208.