Converting two-way nondeterministic unary automata into simpler automata.
From MaRDI portal
Publication:1401239
DOI10.1016/S0304-3975(02)00403-6zbMath1045.68080WikidataQ57380802 ScholiaQ57380802MaRDI QIDQ1401239
Viliam Geffert, Carlo Mereghetti, Giovanni Pighizzini
Publication date: 17 August 2003
Published in: Theoretical Computer Science (Search for Journal in Brave)
Related Items (35)
On the Size of Two-Way Reasonable Automata for the Liveness Problem ⋮ Complementing two-way finite automata ⋮ Homomorphisms on graph-walking automata ⋮ On the Determinization Blowup for Finite Automata Recognizing Equal-Length Languages ⋮ Complexity of multi-head finite automata: origins and directions ⋮ Homomorphisms and inverse homomorphisms on graph-walking automata ⋮ On the transformation of two-way finite automata to unambiguous finite automata ⋮ On the Size of Two-Way Reasonable Automata for the Liveness Problem ⋮ Descriptional complexity of limited automata ⋮ State complexity of operations on two-way finite automata over a unary alphabet ⋮ Descriptional complexity of two-way pushdown automata with restricted head reversals ⋮ TESTING THE DESCRIPTIONAL POWER OF SMALL TURING MACHINES ON NONREGULAR LANGUAGE ACCEPTANCE ⋮ Two-way automata making choices only at the endmarkers ⋮ Hyper-minimizing minimized deterministic finite state automata ⋮ Translation from classical two-way automata to pebble two-way automata ⋮ On the transformation of two-way deterministic finite automata to unambiguous finite automata ⋮ Magic numbers in the state hierarchy of finite automata ⋮ Two-Way Automata versus Logarithmic Space ⋮ Nondeterminism Is Essential in Small 2FAs with Few Reversals ⋮ On the Length of Shortest Strings Accepted by Two-way Finite Automata ⋮ On the state complexity of operations on two-way finite automata ⋮ Removing nondeterminism in constant height pushdown automata ⋮ Oblivious two-way finite automata: decidability and complexity ⋮ Two-way automata versus logarithmic space ⋮ SIMULATIONS OF UNARY ONE-WAY MULTI-HEAD FINITE AUTOMATA ⋮ Two-way unary automata versus logarithmic space ⋮ Investigations on Automata and Languages Over a Unary Alphabet ⋮ Semitensor product approach to controllability, reachability, and stabilizability of probabilistic finite automata ⋮ Size Complexity of Two-Way Finite Automata ⋮ DETERMINISM VS. NONDETERMINISM FOR TWO-WAY AUTOMATA: Representing the Meaning of States by Logical Formulæ ⋮ On Simulation Cost of Unary Limited Automata ⋮ Deterministic one-way simulation of two-way deterministic finite automata over small alphabets ⋮ Converting nondeterministic two-way automata into small deterministic linear-time machines ⋮ State complexity of GF(2)-operations on unary languages ⋮ Two-way automata characterizations of L/poly versus NL
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Finite automata and unary languages
- A note on the reduction of two-way automata to one-way automata
- Lower bounds on the size of sweeping automata
- Two-way deterministic finite automata are exponentially more succinct than sweeping automata
- Optimal Simulations between Unary Automata
- Two-way automaton computations
- Nondeterministic Computations in Sublogarithmic Space and Space Constructibility
- Nondeterminism and the size of two way finite automata
This page was built for publication: Converting two-way nondeterministic unary automata into simpler automata.
