Halting Stack Automata

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Halting Stack Automata

Full text

Pdf (1.07 MB)

Source

Journal of the ACM (JACM) archive
Volume 16 , Issue 4 (October 1969) table of contents

Pages: 550 - 563

Year of Publication: 1969

ISSN:0004-5411

Author

J. D. Ullman

Department of Electrical Engineering, Princeton University, Princeton, N.J. and Bell Telephone Laboratories, Inc., Murray Hill, New Jersey

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 24, Citation Count: 1

Additional Information:

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

ABSTRACT

It is shown that every two-way (deterministic) stack automaton language is accepted by a two-way (deterministic) stack automaton which for each input has a bound on the length of a valid computation. As a consequence, two-way deterministic stack languages are closed under complementation.

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	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]
	2	HOPCROFT, J. E., AND ULLMAN, J. D. Nonerasing stack automata. J. Comput. Syst. Sci. 1, 2 (Aug. 1967), 166-186.
	3	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]
	4	HOPCROFT, J. E., AND ULLMAN, J .D . Sets accepted by one-way stack automata are context sensitive. InJorm. Contr. 15, 2 (Aug. 1968), 114-133.
	5	HOPCROFT, J. E., AND ULLMAN, J. D. Deterministic stack automata and the quotient operator. J. Comput. Syst. Sci. 2, 1 (June 1968), 1-12.
	6	GRAY, J. N., HARRISON, M. A., AND IBARRt, O. Two-way pushdown automata. Inform. Contr. 11 (1967) 30--70.
	7	J. E. Hopcroft , J. D. Ullman, Some Results on Tape-Bounded Turing Machines, Journal of the ACM (JACM), v.16 n.1, p.168-177, Jan. 1969 [doi>10.1145/321495.321508]
	8	GINSnUR, S., AND HOPCROFT, J. E. Two-way balloon automata and AFL. Rep. TM 738/042/00, System Development Corp., Santa Monica, Calif.
	9	John E. Hopcroft , Jeffrey D. Ullman, Formal languages and their relation to automata, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1969