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

DOI10.1016/j.ic.2022.104956OpenAlexW4294550790MaRDI QIDQ6186312

Alexander Okhotin, Semyon Petrov

Publication date: 2 February 2024

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2022.104956

zbMATH Keywords

two-way finite automatadescriptional complexityunambiguous finite automata

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• 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.
• On the transformation of two-way deterministic finite automata to unambiguous finite automata
• Two-way automata characterizations of L/poly versus NL
• Complementing two-way finite automata
• On complementing unambiguous automata and graphs with many cliques and cocliques
• Optimal Simulations between Unary Automata
• 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

This page was built for publication: On the transformation of two-way finite automata to unambiguous finite automata