Converting two-way nondeterministic unary automata into simpler automata.
From MaRDI portal
Publication:1401239
Recommendations
Cites work
- scientific article; zbMATH DE number 3664335 (Why is no real title available?)
- scientific article; zbMATH DE number 3754072 (Why is no real title available?)
- scientific article; zbMATH DE number 3568031 (Why is no real title available?)
- scientific article; zbMATH DE number 1502111 (Why is no real title available?)
- scientific article; zbMATH DE number 1834680 (Why is no real title available?)
- A note on the reduction of two-way automata to one-way automata
- Finite automata and unary languages
- Lower bounds on the size of sweeping automata
- Nondeterminism and the size of two way finite automata
- Nondeterministic Computations in Sublogarithmic Space and Space Constructibility
- Optimal simulations between unary automata
- Two-way automaton computations
- Two-way deterministic finite automata are exponentially more succinct than sweeping automata
Cited in
(42)- Deterministic one-way simulation of two-way deterministic finite automata over small alphabets
- Hyper-minimizing minimized deterministic finite state automata
- Input- or output-unary sweeping transducers are weaker than their 2-way counterparts
- Translation from classical two-way automata to pebble two-way automata
- A note on the reduction of two-way automata to one-way automata
- On the transformation of two-way finite automata to unambiguous finite automata
- On the length of shortest strings accepted by two-way finite automata
- On the size of two-way reasonable automata for the liveness problem
- Investigations on automata and languages over a unary alphabet
- Magic numbers in the state hierarchy of finite automata
- 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
- Transforming Two-Way Alternating Finite Automata to One-Way Nondeterministic Automata
- Finite automata and unary languages
- Oblivious two-way finite automata: decidability and complexity
- State complexity of GF(2)-operations on unary languages
- Complementing two-way finite automata
- Two-Way Automata versus Logarithmic Space
- Homomorphisms and inverse homomorphisms on graph-walking automata
- scientific article; zbMATH DE number 1848284 (Why is no real title available?)
- Descriptional complexity of limited automata
- Two-way unary automata versus logarithmic space
- Size Complexity of Two-Way Finite Automata
- Nondeterminism is essential in small 2FAs with few reversals
- scientific article; zbMATH DE number 1502111 (Why is no real title available?)
- TESTING THE DESCRIPTIONAL POWER OF SMALL TURING MACHINES ON NONREGULAR LANGUAGE ACCEPTANCE
- Determinism vs. nondeterminism for two-way automata: representing the meaning of states by logical formulæ
- On the state complexity of operations on two-way finite automata
- Converting nondeterministic two-way automata into small deterministic linear-time machines
- On the transformation of two-way deterministic finite automata to unambiguous finite automata
- Two-way finite automata: old and recent results
- On the size of two-way reasonable automata for the liveness problem
- Semitensor product approach to controllability, reachability, and stabilizability of probabilistic finite automata
- Two-way finite automata: old and recent results
- On the determinization blowup for finite automata recognizing equal-length languages
- On simulation cost of unary limited automata
- Simulations of unary one-way multi-head finite automata
- Homomorphisms on graph-walking automata
- Two-way automata versus logarithmic space
- Removing nondeterminism in constant height pushdown automata
- Two-way automata characterizations of L/poly versus NL
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)
