Two-way automata making choices only at the endmarkers
From MaRDI portal
Publication:476168
DOI10.1016/j.ic.2014.08.009zbMath1309.68119arXiv1110.1263OpenAlexW2476800196WikidataQ61677495 ScholiaQ61677495MaRDI QIDQ476168
Giovanni Pighizzini, Bruno Guillon, Viliam Geffert
Publication date: 28 November 2014
Published in: Information and Computation, Language and Automata Theory and Applications (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1110.1263
Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
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, Converting nondeterministic two-way automata into small deterministic linear-time machines, Two-way automata characterizations of L/poly versus NL
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- An alternating hierarchy for finite automata
- Two-way unary automata versus logarithmic space
- Turing machines that take advice
- Halting space-bounded computations
- Lower bounds on the size of sweeping automata
- Two-way deterministic finite automata are exponentially more succinct than sweeping automata
- Number of quantifiers is better than number of tape cells
- Turing machines with sublogarithmic space
- Converting two-way nondeterministic unary automata into simpler automata.
- Nondeterminism is essential in small two-way finite automata with few reversals
- Relationships between nondeterministic and deterministic tape complexities
- Complementing two-way finite automata
- Two-Way Automata Characterizations of L/poly versus NL
- Two-Way Automata versus Logarithmic Space
- Small Sweeping 2NFAs Are Not Closed Under Complement
- Size Complexity of Two-Way Finite Automata
- Alternation
- Making Nondeterminism Unambiguous
- Las Vegas versus determinism for one-way communication complexity, finite automata, and polynomial-time computations
- Nondeterminism and the size of two way finite automata
