Characterizations of Pushdown Machines in Terms of Time-Bounded Computers

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Characterizations of Pushdown Machines in Terms of Time-Bounded Computers

Full text

Pdf (1.20 MB)

Source

Journal of the ACM (JACM) archive
Volume 18 , Issue 1 (January 1971) table of contents

Pages: 4 - 18

Year of Publication: 1971

ISSN:0004-5411

Author

Stephen A. Cook

Department of Computer Science, University of Toronto, Toronto, Ontario, Canada and University of California, Department of Mathematics, Berkeley, California

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 62, Citation Count: 42

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/321623.321625 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	AHO, A. V., HOPCROFT, J. E., AND ULLMAN, J.D. Time and tape complexity of pushdown automaton languages. Inform. Contr. 13, 3 (Sept. 1968), 186-206.
	2	COBHAM, A. The intrinsic computational difficulty of functions. Proc. 1964 Internat. Congr. for Logic, Methodology, and Philosophy of Science, North-Holland, Amsterdam, pp. 24--30.
	3	COLE, S. N. Real-time computation by n-dimensional iterative arrays of finite-state machines. IEEE Conf. Record of 1966 Seventh Annual Syrup. on Switching and Automata Theory, Oct. 1966, pp. 53-77.
	4	Stephen A. Cook, Variations on pushdown machines (Detailed Abstract), Proceedings of the first annual ACM symposium on Theory of computing, p.229-231, May 05-07, 1969, Marina del Rey, California, United States [doi>10.1145/800169.805437]
	5	Jay Earley, An efficient context-free parsing algorithm, Communications of the ACM, v.13 n.2, p.94-102, Feb 1970 [doi>10.1145/362007.362035]
	6	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]
	7	GRAY, J., HARRISON, M. A., AND IBARRA, 0. H. Two-way pnshdown automata. Inform. Contr. 11, 1, 2 (July, Aug. 1967), 30--70.
	8	HARRISON, M. A., AND IBARRA, O. H. Multitape and multihead pushdown automata. Inform. Contr. 13, 5 (Nov. 1968), 433-470.
	9	HARTMANIS, J., AND STEARNS, R.E. On the computational complexity of algorithms. Trans. Amer. Math. Soc. 117 (1965), 285-306.
	10	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]
	11	HOPCROFT, J. E., AND ULLMAN, J.D. Nonerasing stack automata. J. Comput. Syst. Sci I, 2 (Aug. 1967), 166-186.
	12	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]
	13	MAGER, G. Writing pushdown acceptors. J. Comput. Syst. Sci. 3, 3 (1969), 276-319.
	14	J. C. Shepherdson , H. E. Sturgis, Computability of Recursive Functions, Journal of the ACM (JACM), v.10 n.2, p.217-255, April 1963 [doi>10.1145/321160.321170]

CITED BY 42

	K. N. King, Measures of parallelism in alternating computation trees (Extended Abstract), Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.189-201, May 11-13, 1981, Milwaukee, Wisconsin, United States
	Eric Allender , Jia Jiao, Depth reduction for noncommutative arithmetic circuits, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.515-522, May 16-18, 1993, San Diego, California, United States
	Neil D. Jones , Alan L. Selman, Turing machines and the spectra of first-order formulas with equality, Proceedings of the fourth annual ACM symposium on Theory of computing, p.157-167, May 01-03, 1972, Denver, Colorado, United States
	Paul Rendell, Turing universality of the game of life, Collision-based computing, Springer-Verlag, London, 2001
	M. Jazayeri , W. F. Ogden , W. C. Rounds, On the complexity of the circularity test for attribute grammars, Proceedings of the 2nd ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.119-129, January 20-22, 1975, Palo Alto, California
	Patrick W. Dymond , Walter L. Ruzzo, Parallel RAMs with owned global memory and deterministic context-free language recognition, Journal of the ACM (JACM), v.47 n.1, p.16-45, Jan. 2000
	Markus Holzer , Pierre McKenzie, Alternating and empty alternating auxiliary stack automata, Theoretical Computer Science, v.299 n.1-3, p.307-326, 18 April 2003
	Mehdi Jazayeri , William F. Ogden , William C. Rounds, The intrinsically exponential complexity of the circularity problem for attribute grammars, Communications of the ACM, v.18 n.12, p.697-706, Dec. 1975
	Neil D. Jones , Steven S. Muchnick, The Complexity of Finite Memory Programs with Recursion, Journal of the ACM (JACM), v.25 n.2, p.312-231, April 1978
	Bruce Litow, Computing a context-free grammar-generating series, Information and Computation, v.169 n.2, p.174-185, September 15, 2001
	Akeo Adachi , Shigeki Iwata , Takumi Kasai, Low level complexity for combinatorial games, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.228-237, May 11-13, 1981, Milwaukee, Wisconsin, United States
	Pavol Dûriš , Zvi Galil, Fooling a two-way automaton or one pushdown store is better than one counter for two way machines (Preliminary Version), Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.177-188, May 11-13, 1981, Milwaukee, Wisconsin, United States
	Joost Engelfriet, Iterated pushdown automata and complexity classes, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.365-373, December 1983
	Stephen A. Cook, An observation on time-storage trade off, Proceedings of the fifth annual ACM symposium on Theory of computing, p.29-33, April 30-May 02, 1973, Austin, Texas, United States
	Georg Gottlob , Nicola Leone , Francesco Scarcello, Computing LOGCFL certificates, Theoretical Computer Science, v.270 n.1-2, p.761-777, January
	I. H. Sudborough, On the Tape Complexity of Deterministic Context-Free Languages, Journal of the ACM (JACM), v.25 n.3, p.405-414, July 1978
	Eric W. Allender, P-uniform circuit complexity, Journal of the ACM (JACM), v.36 n.4, p.912-928, Oct. 1989
	Stephen A. Cook, The complexity of theorem-proving procedures, Proceedings of the third annual ACM symposium on Theory of computing, p.151-158, May 03-05, 1971, Shaker Heights, Ohio, United States
	Nicholas Pippenger, Comparative schematology and pebbling with auxiliary pushdowns (Preliminary Version), Proceedings of the twelfth annual ACM symposium on Theory of computing, p.351-356, April 28-30, 1980, Los Angeles, California, United States
	H. Venkateswaran, Properties that characterize LOGCFL, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.141-150, January 1987, New York, New York, United States
	Georg Gottlob , Nicola Leone , Francesco Scarcello, The complexity of acyclic conjunctive queries, Journal of the ACM (JACM), v.48 n.3, p.431-498, May 2001
	I. H. Sudborough, Separating tape bounded auxiliary pushdown automata classes, Proceedings of the ninth annual ACM symposium on Theory of computing, p.208-217, May 04-04, 1977, Boulder, Colorado, United States
	H. B. Hunt, III , T. G. Szymanski, On the complexity of grammar and related problems, Proceedings of seventh annual ACM symposium on Theory of computing, p.54-65, May 05-07, 1975, Albuquerque, New Mexico, United States
	I. H. Sudborough, On deterministic context-free languages, multihead automata, and the power of an auxiliary pushdown store, Proceedings of the eighth annual ACM symposium on Theory of computing, p.141-148, May 03-05, 1976, Hershey, Pennsylvania, United States
	Klaus Aehlig , Helmut Schwichtenberg, A syntactical analysis of non-size-increasing polynomial time computation, ACM Transactions on Computational Logic (TOCL), v.3 n.3, p.383-401, July 2002
	Walter L. Ruzzo, Tree-size bounded alternation(Extended Abstract), Proceedings of the eleventh annual ACM symposium on Theory of computing, p.352-359, April 30-May 02, 1979, Atlanta, Georgia, United States
	Joep Rous, Computational aspects of M-grammars, Proceedings of the fifth conference on European chapter of the Association for Computational Linguistics, p.210-215, April 09-11, 1991, Berlin, Germany
	H. B. Hunt, III, On the time and tape complexity of languages I, Proceedings of the fifth annual ACM symposium on Theory of computing, p.10-19, April 30-May 02, 1973, Austin, Texas, United States
	Jik H. Chang , Oscar H. Ibarra , Anastasios Vergis, On the power of one-way communication, Journal of the ACM (JACM), v.35 n.3, p.697-726, July 1988
	J. Y. Marion, Analysing the implicit complexity of programs, Information and Computation, v.183 n.1, p.2-18, May 25, 2003
	N. Markey , Ph. Schnoebelen, A PTIME-complete matching problem for SLP-compressed words, Information Processing Letters, v.90 n.1, p.3-6, 15 April 2004
	Dale Myers, The random access hierarchy, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.355-364, December 1983
	Neil D. Jones , Steven S. Muchnick, Even simple programs are hard to analyze, Proceedings of the 2nd ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.106-118, January 20-22, 1975, Palo Alto, California
	E. Böhler , C. Glaßer , B. Schwarz , K. W. Wagner, Generation problems, Theoretical Computer Science, v.345 n.2-3, p.260-295, 22 November 2005
	Lane A. Hemaspaandra, SIGACT news complexity theory column 42, ACM SIGACT News, v.34 n.4, December 2003
	Bodo Manthey , Rüdiger Reischuk, The intractability of computing the Hamming distance, Theoretical Computer Science, v.337 n.1-3, p.331-346, 9 June 2005
	Luc Segoufin, Typing and querying XML documents: some complexity bounds, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.167-178, June 09-11, 2003, San Diego, California
	Lane A. Hemaspaandra, SIGACT news complexity theory column 35, ACM SIGACT News, v.33 n.1, March 2002
	Roberto M. Amadio, Synthesis of max-plus quasi-interpretations, Fundamenta Informaticae, v.65 n.1-2, p.29-60, January 2005
	Neil D. Jones, The expressive power of higher-order types or, life without CONS, Journal of Functional Programming, v.11 n.1, p.55-94, January 2001
	Joost Engelfriet, The complexity of the circularity problem for attribute grammars: a note on a counterexample for a simpler construction, ACM SIGACT News, v.20 n.3, p.57-59, July 1989
	Berke Durak, Two-way finite automata with a write-once track, Journal of Automata, Languages and Combinatorics, v.12 n.1, p.97-115, January 2007