An alternating hierarchy for finite automata
From MaRDI portal
Publication:442279
DOI10.1016/J.TCS.2012.04.044zbMATH Open1255.68095OpenAlexW2061996338MaRDI QIDQ442279FDOQ442279
Authors: Viliam Geffert 
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
Recommendations
- Constructions for alternating finite automata∗
- Alternating nonzero automata
- Alternating multihead finite automata
- scientific article; zbMATH DE number 3911710
- Alternating finite automata with limited universal branching
- scientific article; zbMATH DE number 3866588
- Alternating finite automata on \(\omega\)-words
- Alternating finite automata and star-free languages
- Alternating tree automata
Formal languages and automata (68Q45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- On the state complexity of reversals of regular languages
- Nondeterministic Space is Closed under Complementation
- Alternation
- The method of forced enumeration for nondeterministic automata
- Nondeterministic Computations in Sublogarithmic Space and Space Constructibility
- Title not available (Why is that?)
- Title not available (Why is that?)
- On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata
- Optimal simulations between unary automata
- Size Complexity of Two-Way Finite Automata
- Nondeterminism and the size of two way finite automata
- Erratum to: Some observations concerning alternating Turing machines using small space
- The alternation hierarchy for sublogarithmic space is infinite
- ${\text{ASPACE}}(o(\log \log n))$ is Regular
- A hierarchy that does not collapse : alternations in low level space
- The Sublogarithmic Alternating Space World
- Title not available (Why is that?)
Cited In (20)
- Synchronized finite automata and 2DFA reductions
- Implementation and Application of Automata
- A Playful Glance at Hierarchical Questions for Two-Way Alternating Automata
- Probabilism versus Alternation for Automata
- A symbolic decision procedure for symbolic alternating finite automata
- Title not available (Why is that?)
- Alternation in two-way finite automata
- Possibilities of various types of alternating automata
- Title not available (Why is that?)
- Alternating finite automata on \(\omega\)-words
- Alternating finite automata and star-free languages
- Two-way automata making choices only at the endmarkers
- Unambiguous and co-nondeterministic computations of finite automata and pushdown automata families and the effects of multiple counters
- Complement for two-way alternating automata
- Existential and universal width of alternating finite automata
- Advice hierarchies among finite automata
- On the state complexity of operations on two-way finite automata
- Width measures of alternating finite automata
- Converting finite width AFAs to nondeterministic and universal finite automata
- Title not available (Why is that?)
This page was built for publication: An alternating hierarchy for finite automata
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q442279)
