Alternation bounded auxiliary pushdown automata

DOI10.1016/S0019-9958(84)80029-7zbMath0589.68058MaRDI QIDQ3718176

Richard J. Lipton, Richard E. Ladner, Larry J. Stockmeyer

Publication date: 1984

Published in: Information and Control (Search for Journal in Brave)

zbMATH Keywords

alternationsnondeterministic Turing machineshierarchy of classes of languages accepted by pushdown automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (7)

Alternating and empty alternating auxiliary stack automata. ⋮ A grammatical characterization of alternating pushdown automata ⋮ Empty alternation ⋮ A Space Lower Bound for Acceptance by One-Way Π₂-Alternating Machines ⋮ Characterizing the polynomial hierarchy by alternating auxiliary pushdown automata ⋮ A characterization of exponential-time languages by alternating context- free grammars ⋮ Lower bounds for multiplayer noncooperative games of incomplete information

This page was built for publication: Alternation bounded auxiliary pushdown automata