Alternating Pushdown and Stack Automata
- 1 February 1984
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 13 (1) , 135-155
- https://doi.org/10.1137/0213010
Abstract
The classes of languages accepted by alternating pushdown automata, alternating stack automata, and alternating nonerasing stack automata, both with and without an auxiliary space bounded worktape, are characterized in terms of complexity classes defined by time bounded deterministic Turing machines. It is also shown that alternating 2-way finite state machines accept only regular languages.Keywords
This publication has 17 references indexed in Scilit:
- (Semi)alternating stack automataTheory of Computing Systems, 1981
- Computing a perfect strategy for n × n chess requires time exponential in nJournal of Combinatorial Theory, Series A, 1981
- AlternationJournal of the ACM, 1981
- The complexity of logical theoriesTheoretical Computer Science, 1980
- Path Systems: Constructions, Solutions and ApplicationsSIAM Journal on Computing, 1980
- Propositional dynamic logic of regular programsJournal of Computer and System Sciences, 1979
- Characterizations of Pushdown Machines in Terms of Time-Bounded ComputersJournal of the ACM, 1971
- Nonerasing stack automataJournal of Computer and System Sciences, 1967
- Two-way pushdown automataInformation and Control, 1967
- Stack automata and compilingJournal of the ACM, 1967