Two results on one-way stack automata
- 1 January 1967
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
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
This publication has 6 references indexed in Scilit:
- Sets accepted by one-way stack automata are context sensitiveInformation and Control, 1968
- Deterministic stack automata and the quotient operatorJournal of Computer and System Sciences, 1968
- One-way stack automataJournal of the ACM, 1967
- Stack automata and compilingJournal of the ACM, 1967
- One-way stack automata Extended abstract7th Annual Symposium on Switching and Automata Theory (swat 1966), 1966
- Classes of languages and linear-bounded automataInformation and Control, 1964