Characterizing the polynomial hierarchy by alternating auxiliary pushdown automata
From MaRDI portal
Publication:3816981
DOI10.1051/ita/1989230100871zbMath0665.68038MaRDI QIDQ3816981
Publication date: 1989
Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)
Full work available at URL: https://eudml.org/doc/92326
complexity theory; PSPACE; machine model; pushdown store; alternating auxiliary pushdown hierarchy; logarithmic alternation hierarchy; pushdown automata with unbounded alternation
68Q25: Analysis of algorithms and problem complexity
68Q45: Formal languages and automata
03D15: Complexity of computation (including implicit computational complexity)
Related Items
Empty alternation, A very hard log-space counting class, Properties of probabilistic pushdown automata, Alternating and empty alternating auxiliary stack automata.
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The polynomial-time hierarchy
- Checking automata and one-way stack languages
- Alternating Pushdown and Stack Automata
- Alternation bounded auxiliary pushdown automata
- Nondeterministic Space is Closed under Complementation
- Alternation
- On the Tape Complexity of Deterministic Context-Free Languages
- Characterizations of Pushdown Machines in Terms of Time-Bounded Computers