Two-Way Automata Characterizations of L/poly versus NL

DOI10.1007/978-3-642-30642-6_21zbMATH Open1360.68476DBLPconf/csr/KapoutsisP12OpenAlexW180756232WikidataQ61677512 ScholiaQ61677512MaRDI QIDQ2907503FDOQ2907503

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

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
• 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

Mathematics Subject Classification ID

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

Cited In (3)

• Oblivious two-way finite automata: decidability and complexity
• Two-way automata making choices only at the endmarkers
• 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)