Alternating and empty alternating auxiliary stack automata.
From MaRDI portal
Publication:1874397
DOI10.1016/S0304-3975(02)00326-2zbMath1040.68054OpenAlexW2007370828MaRDI QIDQ1874397
Markus Holzer, Pierre McKenzie
Publication date: 25 May 2003
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0304-3975(02)00326-2
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The complexity of facets (and some facets of complexity)
- Space-bounded hierarchies and probabilistic computations
- The method of forced enumeration for nondeterministic automata
- Nonerasing stack automata
- Checking automata and one-way stack languages
- Relationships between nondeterministic and deterministic tape complexities
- Characterizations of some tape and time complexity classes of Turing machines in terms of multihead and auxiliary stack automata
- Alternating Pushdown and Stack Automata
- Bounded Query Classes
- Alternation bounded auxiliary pushdown automata
- Characterizing the polynomial hierarchy by alternating auxiliary pushdown automata
- Nondeterministic Space is Closed under Complementation
- Alternation
- Relativization of questions about log space computability
- On the Tape Complexity of Deterministic Context-Free Languages
- Empty alternation
- One-way stack automata
- Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
- An Analysis of a Logical Machine Using Parenthesis-Free Notation
This page was built for publication: Alternating and empty alternating auxiliary stack automata.
