Alternating Pushdown and Stack Automata
From MaRDI portal
Recommendations
Cited in
(74)- On the power of deep pushdown stacks
- On the power of alternation in automata theory
- Two-way automata with more than one storage medium
- Relativized alternation and space-bounded computation
- A grammatical characterization of alternating pushdown automata
- Three-dimensional alternating Turing machines with only universal states
- Properties that characterize LOGCFL
- A note on the space complexity of some decision problems for finite automata
- Iterated stack automata and complexity classes
- A survey of space complexity
- A characterization of exponential-time languages by alternating context- free grammars
- A note on two-way probabilistic automata
- Positional simulation of two-way automata: Proof of a conjecture of R. Kannan and generalizations
- Communication for alternating machines
- Properties of probabilistic pushdown automata
- A note on three-dimensional alternating Turing machines with space smaller than m
- Refined simulation of multihead automata
- From bidirectionality to alternation.
- The power of two-way deterministic checking stack automata
- Alternating and empty alternating auxiliary stack automata.
- Alternation in two-way finite automata
- Width measures of alternating finite automata
- Visit-bounded stack automata
- Conjunctive grammars and alternating pushdown automata
- Quantitative vs. weighted automata
- LR(0) conjunctive grammars and deterministic synchronized alternating pushdown automata
- Complexity results for prefix grammars
- scientific article; zbMATH DE number 4131658 (Why is no real title available?)
- A survey on picture-walking automata
- Note on the Succinctness of Deterministic, Nondeterministic, Probabilistic and Quantum Finite Automata
- Nonclosure property of sublogarithmic space-bounded multi-inkdot alternating pushdown automata with only universal states
- Semantic acyclicity on graph databases
- scientific article; zbMATH DE number 4213437 (Why is no real title available?)
- Constructions for alternating finite automata∗
- Some modifications of auxiliary pushdown automata
- On Alternating Phrase-Structure Grammars
- Size Complexity of Two-Way Finite Automata
- scientific article; zbMATH DE number 3907803 (Why is no real title available?)
- scientific article; zbMATH DE number 3926247 (Why is no real title available?)
- Alternation bounded auxiliary pushdown automata
- Yield-languages recognized by alternating tree recognizers
- Time varying pushdown automata
- scientific article; zbMATH DE number 4083011 (Why is no real title available?)
- Characterizing the polynomial hierarchy by alternating auxiliary pushdown automata
- (Semi)alternating stack automata
- scientific article; zbMATH DE number 1759428 (Why is no real title available?)
- Complexity of probabilistic versus deterministic automata
- Complexity results for multi-pebble automata and their logics
- On the power of 1-tape off-line ATMs running in a bounded number of reversals
- Two-way automata and length-preserving homomorphisms
- Space complexity of stack automata models
- Properties of probabilistic pushdown automata
- Reversals and alternation
- Alternating space is closed under complement and other simulations for sublogarithmic space
- ON ALTERNATING PHRASE-STRUCTURE GRAMMARS
- On dynamics of automata with a stack
- State-complexity of finite-state devices, state compressibility and incompressibility
- On the complexity of typechecking top-down XML transformations
- On state-alternating context-free grammars
- A lower bound for probabilistic algorithms for finite state machines
- Complement for two-way alternating automata
- Unary coded PSPACE-complete languages in \(\mathrm{ASPACE}(\log\log n)\)
- Unary coded PSPACE-complete languages in \(\mathrm{ASPACE}(\log\log n)\)
- Lower bounds for multiplayer noncooperative games of incomplete information
- Visit-bounded stack automata
- Generalizations of Checking Stack Automata: Characterizations and Hierarchies
- Converting finite width AFAs to nondeterministic and universal finite automata
- Space Complexity of Stack Automata Models
- Advocating ownership
- Derivatives on graphs for the positive calculus of relations with transitive closure
- Improved upper bounds for determinizing NIDPDAs with limited nondeterminism
- Existential and universal width of alternating finite automata
- Maximal universal width of an AFA is NP-hard
- LR(0) conjunctive grammars and deterministic synchronized alternating pushdown automata
This page was built for publication: Alternating Pushdown and Stack Automata
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3325044)
