DocumentCode
3263511
Title
Two results on one-way stack automata
Author
Hopcroft, J.E. ; Ullman, J.D.
fYear
1967
fDate
18-20 Oct. 1967
Firstpage
37
Lastpage
44
Abstract
A stack automaton is a device with a pushdown list which can be read by its storage head in a read only mode. In this paper, we show two properties of stack automata with a one-way input. (1) If a language is accepted by a nondeterministic one-way stack automaton, then it is accepted by a deterministic linear bounded automaton. (2) If a language, L, is accepted by a deterministic one-way stack automaton, and R is a regular set, then L/R = {x for some y in R, xy is in L} is accepted by a deterministic one-way stack automaton.
Keywords
Automata;
fLanguage
English
Publisher
ieee
Conference_Titel
Switching and Automata Theory, 1967. SWAT 1967. IEEE Conference Record of the Eighth Annual Symposium on
Conference_Location
Austin, TX, USA
Type
conf
DOI
10.1109/FOCS.1967.37
Filename
5397225
Link To Document