Variations on pushdown machines (Detailed Abstract)

ABSTRACT

A class of machines called auxiliary pushdown machines is introduced. Several types of pushdown automata, including stack automata, are characterized in terms of these machines. The computing power of each class of machines in question is characterized in terms of time bounded Turing machines, and corollaries are derived which answer some open questions in the field.

REFERENCES

• 1: J. Hartmanis, P.M. Lewis II, R.E. Stearns. Classifications of Computations by Time and Memory Requirements, Proc. IFIP Congr. 65(1965), 31-35.
• 2: M.A. Harrison and O.H. Ibarra. Multitape and Multihead Pushdown Automata. To appear in Information and Control.
• 3: G. Mager. Writing Pushdown Acceptors. Report No. TM-738/047/00, System Development Corporation, Santa Monica, California. May, 1968.
• 4: Seymour Ginsburg , Sheila A. Greibach , Michael A. Harrison, Stack automata and compiling, Journal of the ACM (JACM), v.14 n.1, p.172-201, Jan. 1967 [doi>10.1145/321371.321385]
• 5: A.V. Aho, J.E. Hopcroft, and J.D. Ullman. Time and Tape Complexity of Pushdown Automaton Languages. Information and Control 13, 186-206 (1968).
• 6: J.E. Hopcroft and J.D. Ullman. Nonerasing Stack Automata. J. of Computer and System Sciences, Vol. l, No. 2, 166-686 (August, 1967).
• 7: F. C. Hennie , R. E. Stearns, Two-Tape Simulation of Multitape Turing Machines, Journal of the ACM (JACM), v.13 n.4, p.533-546, Oct. 1966 [doi>10.1145/321356.321362]
• 8: Alan Cobham. The Intrinsic Computational Difficulty of Functions. Proceedings of the 1964 International Congress for Logic, Methodology, and Philosophy of Science, North-Holland Publishing Co., Amsterdam, 24-30.
• 9: Donald E. Knuth , Richard H. Bigelow, Programming Language for Automata, Journal of the ACM (JACM), v.14 n.4, p.615-635, Oct. 1967 [doi>10.1145/321420.321421]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Automata (e.g., finite, push-down, resource-bounded)

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Relations among complexity measures

General Terms:
Algorithms, Measurement, Theory