The Complexity of Finite Memory Programs with Recursion

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The Complexity of Finite Memory Programs with Recursion

Full text

Pdf (533 KB)

Source

Journal of the ACM (JACM) archive
Volume 25 , Issue 2 (April 1978) table of contents

Pages: 312 - 231

Year of Publication: 1978

ISSN:0004-5411

Authors

Neil D. Jones	Department of Computer Science, The University of Kansas, Lawrence, KS and University of Aarhus, Denmark
Steven S. Muchnick	Department of Computer Science, The University of Kansas, Lawrence, KS

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 19, Citation Count: 2

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/322063.322074 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	Stephen A. Cook, Characterizations of Pushdown Machines in Terms of Time-Bounded Computers, Journal of the ACM (JACM), v.18 n.1, p.4-18, Jan. 1971 [doi>10.1145/321623.321625]
	2	John E. Hopcroft , Jeffrey D. Ullman, Formal languages and their relation to automata, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1969
	3	Neil D. Jones , Steven S. Muchnick, Even Simple Programs Are Hard To Analyze, Journal of the ACM (JACM), v.24 n.2, p.338-350, April 1977 [doi>10.1145/322003.322016]
	4	David Bruce Lomet, A Formalization of Transition Diagram Systems, Journal of the ACM (JACM), v.20 n.2, p.235-257, April 1973 [doi>10.1145/321752.321756]
	5	Marvin Lee Minsky, Computation: Finite and Infinite Machines, Prentice-Hall, Inc., Upper Saddle River, NJ, 1967
	6	J. W. Backus , F. L. Bauer , J. Green , C. Katz , J. McCarthy , A. J. Perlis , H. Rutishauser , K. Samelson , B. Vauquois , J. H. Wegstein , A. van Wijngaarden , M. Woodger , P. Naur, Revised report on the algorithm language ALGOL 60, Communications of the ACM, v.6 n.1, p.1-17, Jan. 1963 [doi>10.1145/366193.366201]
	7	TIXIER, V Recurs~ve Functions of Regular Expressions m Language Analysis Tech Rep CS-58, Comptr ScL Dept, Stanford Umverstty, Stanford, Cahf, March 1967

CITED BY 2

	Torben Mogensen , David Schmidt , I. Hal Sudborough, Preface, The essence of computation: complexity, analysis, transformation, Springer-Verlag New York, Inc., New York, NY, 2002
	Eitan M. Gurari, Decidable problems for powerful programs, Journal of the ACM (JACM), v.32 n.2, p.466-483, April 1985