Two-Way Automata Characterizations of L/poly versus NL

DOI10.1007/978-3-642-30642-6_21MaRDI QIDQ2907503zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Giovanni Pighizzini, Christos 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)

Recommendations

• Two-way automata characterizations of L/poly versus NL
• A characterisation of NL/poly via nondeterministic finite automata
• Two-way automata over locally finite semirings
• Two-way finite automata: old and recent results
• Two-way finite automata: old and recent results
• scientific article; zbMATH DE number 177806
• Two-way automata and length-preserving homomorphisms
• Two-way representations and weighted automata
• Two-way automata versus logarithmic space
• Two-Way Automata versus Logarithmic Space

Cited in

(3)

• Two-way automata characterizations of L/poly versus NL
• Oblivious two-way finite automata: decidability and complexity
• A characterisation of NL/poly via nondeterministic finite automata

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2907503)