Two-way automata characterizations of L/poly versus NL

DOI10.1007/s00224-014-9560-xzbMath1343.68141OpenAlexW2076657210WikidataQ61677488 ScholiaQ61677488MaRDI QIDQ2354593

Christos A. Kapoutsis, Giovanni Pighizzini

Publication date: 20 July 2015

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-014-9560-x

zbMATH Keywords

two-way finite automatalogarithmic spacedescriptional complexitystructural complexity

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (7)

Homomorphisms on graph-walking automata ⋮ Unambiguity and fewness for nonuniform families of polynomial-size nondeterministic finite automata ⋮ On the transformation of two-way finite automata to unambiguous finite automata ⋮ 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 ⋮ Converting nondeterministic two-way automata into small deterministic linear-time machines

Cites Work

• Unnamed Item
• Unnamed Item
• Two-way automata making choices only at the endmarkers
• Two-way unary automata versus logarithmic space
• Converting two-way nondeterministic unary automata into simpler automata.
• Two-way automata versus logarithmic space
• Relationships between nondeterministic and deterministic tape complexities
• Complementing two-way finite automata
• Size Complexity of Two-Way Finite Automata
• Describing Periodicity in Two-Way Deterministic Finite Automata Using Transformation Semigroups
• Nondeterminism and the size of two way finite automata

This page was built for publication: Two-way automata characterizations of L/poly versus NL