Multitape AFA

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Multitape AFA

Full text

Pdf (1.43 MB)

Source

Journal of the ACM (JACM) archive
Volume 19 , Issue 2 (April 1972) table of contents

Pages: 193 - 221

Year of Publication: 1972

ISSN:0004-5411

Authors

Seymour Ginsburg	University of California at Los Angeles, Los Angeles, California and Department of System Science, Los Angeles, CA
Sheila Greibach	University of Southern California, Computer Science Program, Olin Hall of Engineering, Los Angeles, CA

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 0, Downloads (12 Months): 15, 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/321694.321695 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	Alfred V. Aho, Nested Stack Automata, Journal of the ACM (JACM), v.16 n.3, p.383-406, July 1969 [doi>10.1145/321526.321529]
	2	CHOMSKY, N., AND SCIUTZENBERGER, M.P. The algebraic theory of context-free languages. In Computer-Programming and Formal Systems, P. Braffort and D. Hirschberg, eds., North-Holland, Amsterdam, 1968, pp. 118-161.
	3	FISCHER, P .C . Turing machines with restricted memory access. Inform. Contr. 9 (1966), 364-379.
	4	FISCHER, P. C., MEYER, A. K., AND ROSENBERG, A.L. Counter machines and counter languages. Math. Syst. Theory 2 (1968), 265-283.
	5	GINSBUR6, S., AND GREInACH, S.A. Abstract families of languages. In Studies in Abstract Families of Languages, Memoir 87, Amer. Math. Soc., Providence, R. I., 1969, pp. 1-32.
	6	Seymour Ginsburg , Sheila A. Greibach , Michael A. Harrison, One-way stack automata, Journal of the ACM (JACM), v.14 n.2, p.389-418, April 1967 [doi>10.1145/321386.321403]
	7	GINSnUR, S., GREIBACH, S. A., AND HOPCROFT, J . Pre-AFL. In Studies in Abstract Families of Languages, Memoir 87, Amer. Math. Soc., Providence, R. I., 1969, pp. 41-51.
	8	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 [doi>10.1145/321466.321475]
	9	GINSBURG, S., AND HOPCROFT, J. Images of AFL under certain families of homonmrphisms. Math. Syst. Theory 5 (1971), 216-227.
	10	GINSBURG, S., AND SPANIER, E .H . Finite-turn pushdown automata. SIAM J. Connlr. 4 (1966), 429-453.
	11	GINSBURG, S., AND SPANIER, E. H. Control sets on grammars. Math. Sysl. Theory 2 (1968), 159-177.
	12	GINSBURG, S., AND SPANIER, E. H. Derivation-bounded languages. J. Compul. and Syst. Sei. 2 (1968), 228-250.
	13	GINSBURG, S., AND SPANIER, E .H . Substitutions in families of languages. Inform. Sci. 2 (1970), 83-110.
	14	Sheila A. Greibach, A New Normal-Form Theorem for Context-Free Phrase Structure Grammars, Journal of the ACM (JACM), v.12 n.1, p.42-52, Jan. 1965 [doi>10.1145/321250.321254]
	15	Sheila A. Greibach, An Infinite Hierarchy of Context-Free Languages, Journal of the ACM (JACM), v.16 n.1, p.91-106, Jan. 1969 [doi>10.1145/321495.321503]
	16	GREIBACH, S. A. Checking automata and one-way stack languages. J. Comput. and Syst. Sei. 3 (1969), 196-217.
	17	GREIBACH, S.A. Chains of full AFLs. Math. Syst. Theory 4 (1970), 231-242.
	18	HARTMANIS, J., AND HOPCROFT, J. What makes some language theory problems undecidable. J. Comput. and Syst. Sci. 4 (1970), 368 376.
	19	HOPCROFT, J ., AND ULLMAN, J. An approach to a unified theory of automata. Bell Sgsl. Teeh. J. 46 (1967), 1793-1829.
	20	MINSKY, M. Recursive unsolvability of Post's problem of "tag" and other topics in theory of Turing machines. Ann. Math. 74 (1961) 437-455.
	21	NIVAT, M. Transductions des languages de Chomsky. Ann. de L'Insl. Fourier de L'Univ. de Grenoble 18 (1968), 339-456.
	22	YNTEMA, M.K. Inclusion relations among families of context-free languages. Inform. Contr. 10 (1967), 572-597.

CITED BY 2

	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
	Ronald Book , Maurice Nivat , Michael Paterson, Intersections of linear context-free languages and reversal-bounded multipushdown machines (Extended Abstract), Proceedings of the sixth annual ACM symposium on Theory of computing, p.290-296, April 30-May 02, 1974, Seattle, Washington, United States