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

DOI10.1016/J.IC.2022.104956MaRDI QIDQ6186312zbMATH OpenOpenAlexFDO

Authors Semyon Petrov, Alexander Okhotin

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

descriptional complexitytwo-way finite automataunambiguous finite automata

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• A note on the reduction of two-way automata to one-way automata
• A superpolynomial lower bound for the size of non-deterministic complement of an unambiguous automaton
• Complementing two-way finite automata
• Converting two-way nondeterministic unary automata into simpler automata.
• Describing Periodicity in Two-Way Deterministic Finite Automata Using Transformation Semigroups
• DESCRIPTIONAL COMPLEXITY OF NFA OF DIFFERENT AMBIGUITY
• scientific article; zbMATH DE number 863490 (Why is no real title available?)
• scientific article; zbMATH DE number 3254906 (Why is no real title available?)
• Mathematical Foundations of Computer Science 2005
• Nondeterminism and the size of two way finite automata
• On complementing unambiguous automata and graphs with many cliques and cocliques
• On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata
• On the transformation of two-way deterministic finite automata to unambiguous finite automata
• Operations on Unambiguous Finite Automata
• Optimal simulations between unary automata
• State-complexity of finite-state devices, state compressibility and incompressibility
• Two-way automata characterizations of L/poly versus NL
• Unambiguous finite automata over a unary alphabet

Cited in

(3)

• Simulating two-way nondeterministic finite automata over small alphabets by one-way nondeterministic automata
• On the transformation of two-way nondeterministic finite automata to unambiguous finite automata
• Deterministic one-way simulation of two-way deterministic finite automata over small alphabets

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6186312)