Size Complexity of Two-Way Finite Automata
From MaRDI portal
Publication:3637213
DOI10.1007/978-3-642-02737-6_4zbMath1247.68146OpenAlexW1497278126MaRDI QIDQ3637213
Publication date: 7 July 2009
Published in: Developments in Language Theory (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-02737-6_4
Related Items (16)
On the Size of Two-Way Reasonable Automata for the Liveness Problem ⋮ From Two-Way to One-Way Finite Automata—Three Regular Expression-Based Methods ⋮ Size complexity of rotating and sweeping automata ⋮ Probabilism versus Alternation for Automata ⋮ Unambiguity and fewness for nonuniform families of polynomial-size nondeterministic finite automata ⋮ On the Size of Two-Way Reasonable Automata for the Liveness Problem ⋮ An alternating hierarchy for finite automata ⋮ Two-way automata making choices only at the endmarkers ⋮ State complexity characterizations of parameterized degree-bounded graph connectivity, sub-linear space computation, and the linear space hypothesis ⋮ New size hierarchies for two way automata ⋮ Removing nondeterminism in constant height pushdown automata ⋮ Two-way unary automata versus logarithmic space ⋮ Complement for two-way alternating automata ⋮ Alternation in two-way finite automata ⋮ Nonuniform families of polynomial-size quantum finite automata and quantum logarithmic-space computation with polynomial-size advice ⋮ Two-way automata characterizations of L/poly versus NL
Cites Work
- Finite automata and unary languages
- Halting space-bounded computations
- Lower bounds on the size of sweeping automata
- Converting two-way nondeterministic unary automata into simpler automata.
- Amplification of slight probabilistic advantage at absolutely no cost in space
- On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata
- Complementing two-way finite automata
- Alternating Pushdown and Stack Automata
- A Time Complexity Gap for Two-Way Probabilistic Finite-State Automata
- On the Size Complexity of Rotating and Sweeping Automata
- An Exponential Gap Between LasVegas and Deterministic Sweeping Finite Automata
- Small Sweeping 2NFAs Are Not Closed Under Complement
- Finite state verifiers I
- Two-way automata and length-preserving homomorphisms
- State-complexity of finite-state devices, state compressibility and incompressibility
- Nondeterminism and the size of two way finite automata
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Size Complexity of Two-Way Finite Automata
