One-way stack automata

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

One-way stack automata

Full text

Pdf (1.59 MB)

Source

Journal of the ACM (JACM) archive
Volume 14 , Issue 2 (April 1967) table of contents

Pages: 389 - 418

Year of Publication: 1967

ISSN:0004-5411

Authors

Seymour Ginsburg	System Development Corporation, Santa Monica, California
Sheila A. Greibach	Harvard University, Cambridge, Massachusetts
Michael A. Harrison	University of California, Berkeley, California

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 35, Citation Count: 29

Additional Information:

abstract references cited by index terms collaborative colleagues peer to peer

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/321386.321403 What is a DOI?

ABSTRACT

A number of operations which either preserve sets accepted by one-way stack automata or preserve sets accepted by deterministic one-way stack automata are presented. For example, sequential transduction preserves the former; set complementation, the latter. Several solvability questions are also considered.

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	BAR-HILLEL, Y., PERLE, M., AND SItAMIR, E. On formal properties of simple phrase structure grunm.-ars. Z. Phonelik, Sprachwissen. Kommunikationsforsch. 14 (1961), 143-172; in Y. Bar-Hillel, Language and Information, Addison-Wesley, Rending, Mass., 1965, pp. 116- 150.
	2	CHOMSKY, i . Oil certain formal properties of grammars. Inform. and Contr. (1959), 137-167.
	3	DAvis, M. Computability and Unsolvability. McGraw-Hill, New York, 1958.
	4	GINSRURO, S., AND GREIBACH, S. Deterministic context free langaages. Inform. and Contr. 9 (1966), 62648.
	5	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]
	6	RABIN, M., AND SCOTT, D. Finite automata and their decision problems. IBM J. Res. Develop. 3 (1959), 114-125.

CITED BY 29

	Eugene S. Santos, A Note on Bracketed Grammars, Journal of the ACM (JACM), v.19 n.2, p.222-224, April 1972
	J. D. Ullman, Halting Stack Automata, Journal of the ACM (JACM), v.16 n.4, p.550-563, Oct. 1969
	J. E. Hopcroft , J. D. Ullman, Decidable and Undecidable Questions About Automata, Journal of the ACM (JACM), v.15 n.2, p.317-324, April 1968
	William F. Ogden, Intercalation theorems for stack languages, Proceedings of the first annual ACM symposium on Theory of computing, p.31-42, May 05-07, 1969, Marina del Rey, California, United States
	Michael A. Harrison , Mario Schkolnick, A Grammatical Characterization of One-Way Nondeterministic Stack Languages, Journal of the ACM (JACM), v.18 n.2, p.148-172, April 1971
	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
	W. J. Chandler, Abstract families of deterministic languages, Proceedings of the first annual ACM symposium on Theory of computing, p.21-30, May 05-07, 1969, Marina del Rey, California, United States
	Vaclav Rajlich, Absolutely parallel grammars and two-way deterministic finite-state transducers, Proceedings of the third annual ACM symposium on Theory of computing, p.132-137, May 03-05, 1971, Shaker Heights, Ohio, United States
	Alexander Meduna , Tomáš Masopust, Self-regulating finite automata, Acta Cybernetica, v.18 n.1, p.135-153, January 2007
	Seymour Ginsburg , Sheila Greibach, Multitape AFA, Journal of the ACM (JACM), v.19 n.2, p.193-221, April 1972
	Patrick Shen-Pei Wang, Recognition of two-dimensional patterns, Proceedings of the 1977 annual conference, p.484-489, January 1977
	Seymour Ginsburg , Michael A. Harrison, One-way nondeterministic real-time list-storage languages, Journal of the ACM (JACM), v.15 n.3, p.428-446, July 1968
	Michael J. Fischer, Lambda calculus schemata, ACM SIGPLAN Notices, v.7 n.1, p.104-109, January 1972
	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
	Detlef Wotschke, Degree-languages, polynomial time recognition, and the LBA problem, Proceedings of seventh annual ACM symposium on Theory of computing, p.145-152, May 05-07, 1975, Albuquerque, New Mexico, United States
	Alfred V. Aho, Nested Stack Automata, Journal of the ACM (JACM), v.16 n.3, p.383-406, July 1969
	Alfred V. Aho, Indexed Grammars—An Extension of Context-Free Grammars, Journal of the ACM (JACM), v.15 n.4, p.647-671, Oct. 1968
	Klaus Wich, Sublogarithmic ambiguity, Theoretical Computer Science, v.345 n.2-3, p.473-504, 22 November 2005
	Lane A. Hemaspaandra, SIGACT news complexity theory column 35, ACM SIGACT News, v.33 n.1, March 2002
	Sheila A. Greibach, An Infinite Hierarchy of Context-Free Languages, Journal of the ACM (JACM), v.16 n.1, p.91-106, Jan. 1969
	Paul Rendell, Turing universality of the game of life, Collision-based computing, Springer-Verlag, London, 2001
	Robert C. Berwick, Strong generative capacity, weak generative capacity, and modern linguistic theories, Computational Linguistics, v.10 n.3-4, p.189-202, July-December 1984
	Ronald V. Book , Sheila A. Greibach, Quasi-realtime languages (Extended Abstract), Proceedings of the first annual ACM symposium on Theory of computing, p.15-18, May 05-07, 1969, Marina del Rey, California, United States
	Andreas Klein , Martin Kutrib, Cellular Devices and Unary Languages, Fundamenta Informaticae, v.78 n.3, p.343-368, August 2007
	Thomas Buchholz , Andreas Klein , Martin Kutrib, On interacting automata with limited nondeterminism, Fundamenta Informaticae, v.52 n.1-3, p.15-38, September 2002
	Sheila A. Greibach, Some restrictions on W-grammars, Proceedings of the sixth annual ACM symposium on Theory of computing, p.256-265, April 30-May 02, 1974, Seattle, Washington, United States
	Daniel J. Rosenkrantz, Programmed Grammars and Classes of Formal Languages, Journal of the ACM (JACM), v.16 n.1, p.107-131, Jan. 1969
	Joost Engelfriet , Erik Meineche Schmidt , Jan van Leeuwen, Stack Machines and Classes of Nonnested Macro Languages, Journal of the ACM (JACM), v.27 n.1, p.96-117, Jan. 1980
	Sheila A. Greibach, Jump PDA's, deterministic context-free languages principal AFDLs and polynomial time recognition—(Extended Abstract), Proceedings of the fifth annual ACM symposium on Theory of computing, p.20-28, April 30-May 02, 1973, Austin, Texas, United States