Two-Way Automata Characterizations of L/poly versus NL

DOI10.1007/978-3-642-30642-6_21zbMath1360.68476OpenAlexW180756232WikidataQ61677512 ScholiaQ61677512MaRDI QIDQ2907503

Giovanni Pighizzini, Christos A. Kapoutsis

Publication date: 10 September 2012

Published in: Computer Science – Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-30642-6_21

Mathematics Subject Classification ID

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

Related Items (2)

Two-way automata making choices only at the endmarkers ⋮ Oblivious two-way finite automata: decidability and complexity

This page was built for publication: Two-Way Automata Characterizations of L/poly versus NL