Two-way automata versus logarithmic space
From MaRDI portal
Publication:2254505
DOI10.1007/s00224-013-9465-0zbMath1319.68135OpenAlexW2921992809WikidataQ57380765 ScholiaQ57380765MaRDI QIDQ2254505
Publication date: 5 February 2015
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00224-013-9465-0
two-way finite automatalogarithmic spaceSakoda-Sipser conjecture2D versus 2NL versus NLsub-logarithmic space
Formal languages and automata (68Q45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Two-way non-uniform finite automata, Homomorphisms and inverse homomorphisms on graph-walking automata, Two-Way Non-Uniform Finite Automata, Unambiguity and fewness for nonuniform families of polynomial-size nondeterministic finite automata, On the transformation of two-way deterministic finite automata to unambiguous finite automata, State complexity characterizations of parameterized degree-bounded graph connectivity, sub-linear space computation, and the linear space hypothesis, Nonuniform families of polynomial-size quantum finite automata and quantum logarithmic-space computation with polynomial-size advice, Converting nondeterministic two-way automata into small deterministic linear-time machines, Two-way automata characterizations of L/poly versus NL
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Two-way unary automata versus logarithmic space
- Converting two-way nondeterministic unary automata into simpler automata.
- Relationships between nondeterministic and deterministic tape complexities
- Nondeterminism Is Essential in Small 2FAs with Few Reversals
- Sublogarithmic-space turing machines, nonuniform space complexity, and closure properties
- If deterministic and nondeterministic space complexities are equal for log log n then they are also equal for log n
- Nondeterminism and the size of two way finite automata
- Some Results on Tape-Bounded Turing Machines
- Classes of languages and linear-bounded automata