Two-way automata versus logarithmic space

DOI10.1007/s00224-013-9465-0zbMath1319.68135OpenAlexW2921992809WikidataQ57380765 ScholiaQ57380765MaRDI QIDQ2254505

Christos A. Kapoutsis

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

zbMATH Keywords

two-way finite automatalogarithmic spaceSakoda-Sipser conjecture2D versus 2NL versus NLsub-logarithmic space

Mathematics Subject Classification ID

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