Halting Stack Automata
- 1 October 1969
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 16 (4) , 550-563
- https://doi.org/10.1145/321541.321544
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.Keywords
This publication has 6 references indexed in Scilit:
- Some Results on Tape-Bounded Turing MachinesJournal of the ACM, 1969
- Deterministic stack automata and the quotient operatorJournal of Computer and System Sciences, 1968
- Nonerasing stack automataJournal of Computer and System Sciences, 1967
- Two-way pushdown automataInformation and Control, 1967
- One-way stack automataJournal of the ACM, 1967
- Stack automata and compilingJournal of the ACM, 1967