Converting two-way nondeterministic unary automata into simpler automata.
From MaRDI portal
Publication:1401239
DOI10.1016/S0304-3975(02)00403-6zbMATH Open1045.68080WikidataQ57380802 ScholiaQ57380802MaRDI QIDQ1401239FDOQ1401239
Authors: Viliam Geffert, Carlo Mereghetti, Giovanni Pighizzini 
Publication date: 17 August 2003
Published in: Theoretical Computer Science (Search for Journal in Brave)
Recommendations
Cites Work
- Title not available (Why is that?)
- Nondeterministic Computations in Sublogarithmic Space and Space Constructibility
- 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
- Title not available (Why is that?)
- Nondeterminism and the size of two way finite automata
- Title not available (Why is that?)
- Two-way automaton computations
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (43)
- Translation from classical two-way automata to pebble two-way automata
- Semitensor product approach to controllability, reachability, and stabilizability of probabilistic finite automata
- On the length of shortest strings accepted by two-way finite automata
- Converting nondeterministic two-way automata into small deterministic linear-time machines
- State complexity of GF(2)-operations on unary languages
- Title not available (Why is that?)
- Two-way automata characterizations of L/poly versus NL
- A note on the reduction of two-way automata to one-way automata
- Two-Way Automata versus Logarithmic Space
- Nondeterminism is essential in small 2FAs with few reversals
- Title not available (Why is that?)
- Complexity of multi-head finite automata: origins and directions
- Descriptional complexity of two-way pushdown automata with restricted head reversals
- State complexity of operations on two-way finite automata over a unary alphabet
- Oblivious two-way finite automata: decidability and complexity
- Homomorphisms and inverse homomorphisms on graph-walking automata
- Magic numbers in the state hierarchy of finite automata
- Descriptional complexity of limited automata
- On the transformation of two-way finite automata to unambiguous finite automata
- Transforming Two-Way Alternating Finite Automata to One-Way Nondeterministic Automata
- Complementing two-way finite automata
- Investigations on automata and languages over a unary alphabet
- Input- or output-unary sweeping transducers are weaker than their 2-way counterparts
- TESTING THE DESCRIPTIONAL POWER OF SMALL TURING MACHINES ON NONREGULAR LANGUAGE ACCEPTANCE
- On the transformation of two-way deterministic finite automata to unambiguous finite automata
- Two-way automata versus logarithmic space
- Removing nondeterminism in constant height pushdown automata
- Homomorphisms on graph-walking automata
- Two-way automata making choices only at the endmarkers
- Two-way unary automata versus logarithmic space
- Determinism vs. nondeterminism for two-way automata: representing the meaning of states by logical formulæ
- On the size of two-way reasonable automata for the liveness problem
- On the determinization blowup for finite automata recognizing equal-length languages
- On simulation cost of unary limited automata
- On the size of two-way reasonable automata for the liveness problem
- Hyper-minimizing minimized deterministic finite state automata
- Size Complexity of Two-Way Finite Automata
- Two-way finite automata: old and recent results
- Two-way finite automata: old and recent results
- Simulations of unary one-way multi-head finite automata
- On the state complexity of operations on two-way finite automata
- Deterministic one-way simulation of two-way deterministic finite automata over small alphabets
- Finite automata and unary languages
This page was built for publication: Converting two-way nondeterministic unary automata into simpler automata.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1401239)
