On the transformation of two-way deterministic finite automata to unambiguous finite automata

DOI10.1007/978-3-030-68195-1_7OpenAlexW3130263062MaRDI QIDQ2232267

Alexander Okhotin, Semyon Petrov

Publication date: 4 October 2021

Full work available at URL: https://doi.org/10.1007/978-3-030-68195-1_7

zbMATH Keywords

two-way finite automatadescriptional complexityunambiguous finite automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

Homomorphisms on graph-walking automata ⋮ On the transformation of two-way finite automata to unambiguous finite automata ⋮ Deterministic one-way simulation of two-way deterministic finite automata over small alphabets

Cites Work

• Unnamed Item
• Unambiguous finite automata over a unary alphabet
• A note on the reduction of two-way automata to one-way automata
• Converting two-way nondeterministic unary automata into simpler automata.
• Two-way automata versus logarithmic space
• Complementing two-way finite automata
• Optimal Simulations between Unary Automata
• Relating the Type of Ambiguity of Finite Automata to the Succinctness of Their Representation
• Operations on Unambiguous Finite Automata
• A Superpolynomial Lower Bound for the Size of Non-Deterministic Complement of an Unambiguous Automaton
• Describing Periodicity in Two-Way Deterministic Finite Automata Using Transformation Semigroups
• State-complexity of finite-state devices, state compressibility and incompressibility
• Nondeterminism and the size of two way finite automata
• Mathematical Foundations of Computer Science 2005
• On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata
• DESCRIPTIONAL COMPLEXITY OF NFA OF DIFFERENT AMBIGUITY