Tight lower bounds on the size of sweeping automata
From MaRDI portal
(Redirected from Publication:1604196)
Recommendations
Cites work
- Finite automata and unary languages
- scientific article; zbMATH DE number 3664335 (Why is no real title available?)
- scientific article; zbMATH DE number 3754072 (Why is no real title available?)
- Lower bounds on the size of sweeping automata
- Nondeterminism and the size of two way finite automata
- On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata
- Separating Exponentially Ambiguous Finite Automata from Polynomially Ambiguous Finite Automata
- Two-way deterministic finite automata are exponentially more succinct than sweeping automata
Cited in
(15)- Lower bounds on the area of finite-state machines
- On the descriptional power of heads, counters, and pebbles
- New size hierarchies for two way automata
- Oblivious two-way finite automata: decidability and complexity
- On a compact encoding of the swap automaton
- Nondeterminism is essential in small 2FAs with few reversals
- On the Size Complexity of Rotating and Sweeping Automata
- An Exponential Gap Between LasVegas and Deterministic Sweeping Finite Automata
- Small Sweeping 2NFAs Are Not Closed Under Complement
- Size complexity of rotating and sweeping automata
- Lower bounds on the size of sweeping automata
- A technique for proving lower bounds on the size of sweeping automata
- Complexity of multi-head finite automata: origins and directions
- Sweeping input-driven pushdown automata
- Sweeping input-driven pushdown automata
This page was built for publication: Tight lower bounds on the size of sweeping automata
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1604196)
