Characterizing the polynomial hierarchy by alternating auxiliary pushdown automata

DOI10.1051/ita/1989230100871zbMath0665.68038OpenAlexW344542471MaRDI QIDQ3816981

Bernd Kirsig, Birgit Jenner

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

zbMATH Keywords

complexity theoryPSPACEmachine modelpushdown storealternating auxiliary pushdown hierarchylogarithmic alternation hierarchypushdown automata with unbounded alternation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Complexity of computation (including implicit computational complexity) (03D15)

Related Items

Alternating and empty alternating auxiliary stack automata., Empty alternation, A very hard log-space counting class, Properties of probabilistic pushdown automata

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item