Deterministic one-way simulation of two-way deterministic finite automata over small alphabets
From MaRDI portal
Publication:2096581
DOI10.1007/978-3-030-93489-7_3OpenAlexW4206235945MaRDI QIDQ2096581
Viliam Geffert, Alexander Okhotin
Publication date: 9 November 2022
Full work available at URL: https://doi.org/10.1007/978-3-030-93489-7_3
Related Items (3)
Homomorphisms on graph-walking automata ⋮ Homomorphisms and inverse homomorphisms on graph-walking automata ⋮ Shortest accepted strings for two-way finite automata: approaching the \(2^n\) lower bound
Cites Work
- Unnamed Item
- Unnamed Item
- A note on the reduction of two-way automata to one-way automata
- Converting two-way nondeterministic unary automata into simpler automata.
- Reversibility of computations in graph-walking automata
- On the transformation of two-way deterministic finite automata to unambiguous finite automata
- Optimal Simulations between Unary Automata
- Transforming Two-Way Alternating Finite Automata to One-Way Nondeterministic Automata
- Describing Periodicity in Two-Way Deterministic Finite Automata Using Transformation Semigroups
- Mathematical Foundations of Computer Science 2005
- A Two-Way Automaton with Fewer States than Any Equivalent One-Way Automaton
- On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata
This page was built for publication: Deterministic one-way simulation of two-way deterministic finite automata over small alphabets
