An alternating hierarchy for finite automata
From MaRDI portal
Publication:442279
DOI10.1016/j.tcs.2012.04.044zbMath1255.68095OpenAlexW2061996338MaRDI QIDQ442279
Publication date: 10 August 2012
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2012.04.044
Formal languages and automata (68Q45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (8)
Converting finite width AFAs to nondeterministic and universal finite automata ⋮ Probabilism versus Alternation for Automata ⋮ Existential and universal width of alternating finite automata ⋮ Two-way automata making choices only at the endmarkers ⋮ On the state complexity of operations on two-way finite automata ⋮ Complement for two-way alternating automata ⋮ Alternation in two-way finite automata ⋮ Width measures of alternating finite automata
Cites Work
- On the state complexity of reversals of regular languages
- Erratum to: Some observations concerning alternating Turing machines using small space
- The method of forced enumeration for nondeterministic automata
- The alternation hierarchy for sublogarithmic space is infinite
- Optimal Simulations between Unary Automata
- Size Complexity of Two-Way Finite Automata
- Nondeterministic Space is Closed under Complementation
- Alternation
- Nondeterministic Computations in Sublogarithmic Space and Space Constructibility
- ${\text{ASPACE}}(o(\log \log n))$ is Regular
- A hierarchy that does not collapse : alternations in low level space
- The Sublogarithmic Alternating Space World
- Nondeterminism and the size of two way finite automata
- On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: An alternating hierarchy for finite automata
