Two-way unary automata versus logarithmic space
From MaRDI portal
Publication:549665
DOI10.1016/j.ic.2011.03.003zbMath1216.68143WikidataQ61677514 ScholiaQ61677514MaRDI QIDQ549665
Viliam Geffert, Giovanni Pighizzini
Publication date: 18 July 2011
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ic.2011.03.003
68Q45: Formal languages and automata
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
DETERMINISM VS. NONDETERMINISM FOR TWO-WAY AUTOMATA: Representing the Meaning of States by Logical Formulæ, State complexity characterizations of parameterized degree-bounded graph connectivity, sub-linear space computation, and the linear space hypothesis, Investigations on Automata and Languages Over a Unary Alphabet, Nonuniform families of polynomial-size quantum finite automata and quantum logarithmic-space computation with polynomial-size advice, Two-way automata making choices only at the endmarkers, Oblivious two-way finite automata: decidability and complexity, Two-way automata versus logarithmic space, Two-way automata characterizations of L/poly versus NL, Boolean language operations on nondeterministic automata with a pushdown of constant height
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Turing machines that take advice
- Unary finite automata vs. arithmetic progressions
- Lower bounds on the size of sweeping automata
- Two-way deterministic finite automata are exponentially more succinct than sweeping automata
- Space-bounded reducibility among combinatorial problems
- Turing machines with sublogarithmic space
- Converting two-way nondeterministic unary automata into simpler automata.
- Relationships between nondeterministic and deterministic tape complexities
- Relating the Type of Ambiguity of Finite Automata to the Succinctness of Their Representation
- Size Complexity of Two-Way Finite Automata
- Making Nondeterminism Unambiguous
- State-complexity of finite-state devices, state compressibility and incompressibility
- Nondeterminism and the size of two way finite automata
- DESCRIPTIONAL COMPLEXITY OF NFA OF DIFFERENT AMBIGUITY