Two-way automata making choices only at the endmarkers

DOI10.1007/978-3-642-28332-1_23zbMath1309.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

zbMATH Keywords

regular languagesdescriptional complexitytwo-way automata

Mathematics Subject Classification ID

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 (4)

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

This page was built for publication: Two-way automata making choices only at the endmarkers