Alternating Pushdown and Stack Automata

DOI10.1137/0213010zbMath0538.68039OpenAlexW1971842919WikidataQ56059679 ScholiaQ56059679MaRDI QIDQ3325044

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

Publication date: 1984

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0213010

zbMATH Keywords

pushdown automata deterministic Turing machines stack automata 2-way finite state automata nonerasing stack time complexity classes

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Related Items (49)

Alternating and empty alternating auxiliary stack automata. ⋮ Refined simulation of multihead automata ⋮ State-complexity of finite-state devices, state compressibility and incompressibility ⋮ Conjunctive grammars and alternating pushdown automata ⋮ Semantic Acyclicity on Graph Databases ⋮ Complexity of probabilistic versus deterministic automata ⋮ Relativized alternation and space-bounded computation ⋮ Constructions for alternating finite automata^∗ ⋮ A grammatical characterization of alternating pushdown automata ⋮ On the power of 1-tape off-line ATMs running in a bounded number of reversals ⋮ Three-dimensional alternating Turing machines with only universal states ⋮ From bidirectionality to alternation. ⋮ Converting finite width AFAs to nondeterministic and universal finite automata ⋮ Quantitative vs. weighted automata ⋮ Two-way automata and length-preserving homomorphisms ⋮ On Alternating Phrase-Structure Grammars ⋮ Yield-languages recognized by alternating tree recognizers ⋮ Properties that characterize LOGCFL ⋮ Complexity results for multi-pebble automata and their logics ⋮ A note on the space complexity of some decision problems for finite automata ⋮ Iterated stack automata and complexity classes ⋮ Characterizing the polynomial hierarchy by alternating auxiliary pushdown automata ⋮ LR(0) Conjunctive Grammars and Deterministic Synchronized Alternating Pushdown Automata ⋮ A survey of space complexity ⋮ A characterization of exponential-time languages by alternating context- free grammars ⋮ A note on two-way probabilistic automata ⋮ Alternating space is closed under complement and other simulations for sublogarithmic space ⋮ Positional simulation of two-way automata: Proof of a conjecture of R. Kannan and generalizations ⋮ Complexity results for prefix grammars ⋮ Communication for alternating machines ⋮ On the complexity of typechecking top-down XML transformations ⋮ On state-alternating context-free grammars ⋮ ON ALTERNATING PHRASE-STRUCTURE GRAMMARS ⋮ Lower bounds for multiplayer noncooperative games of incomplete information ⋮ Properties of probabilistic pushdown automata ⋮ A lower bound for probabilistic algorithms for finite state machines ⋮ Complement for two-way alternating automata ⋮ Alternation in two-way finite automata ⋮ LR(0) conjunctive grammars and deterministic synchronized alternating pushdown automata ⋮ Unary coded PSPACE-complete languages in \(\mathrm{ASPACE}(\log\log n)\) ⋮ Unary coded PSPACE-complete languages in \(\mathrm{ASPACE}(\log\log n)\) ⋮ Size Complexity of Two-Way Finite Automata ⋮ Properties of probabilistic pushdown automata ⋮ A Survey on Picture-Walking Automata ⋮ Width measures of alternating finite automata ⋮ A note on three-dimensional alternating Turing machines with space smaller than \(\log m\) ⋮ On the power of alternation in automata theory ⋮ Note on the Succinctness of Deterministic, Nondeterministic, Probabilistic and Quantum Finite Automata ⋮ (Semi)alternating stack automata

This page was built for publication: Alternating Pushdown and Stack Automata