Characterizing the polynomial hierarchy by alternating auxiliary pushdown automata
Open Access
- 1 January 1989
- journal article
- research article
- Published by EDP Sciences in RAIRO - Theoretical Informatics and Applications
- Vol. 23 (1) , 87-99
- https://doi.org/10.1051/ita/1989230100871
Abstract
No abstract availableThis publication has 9 references indexed in Scilit:
- Two applications of complementation via inductive countingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1988
- The logarithmic alternation hierarchy collapses: $$A\Sigma _2^\mathcal{L} = A\Pi _2^\mathcal{L}$$Published by Springer Nature ,1987
- Alternation bounded auxiliary pushdown automataInformation and Control, 1984
- AlternationJournal of the ACM, 1981
- Alternating pushdown automataPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1978
- On the Tape Complexity of Deterministic Context-Free LanguagesJournal of the ACM, 1978
- The polynomial-time hierarchyTheoretical Computer Science, 1976
- Characterizations of Pushdown Machines in Terms of Time-Bounded ComputersJournal of the ACM, 1971
- Checking automata and one-way stack languagesJournal of Computer and System Sciences, 1969