Two-way automata and one-tape machines. Read only versus linear time

DOI10.1007/978-3-319-98654-8_30OpenAlexW2886120347MaRDI QIDQ1622984FDOQ1622984

Authors: Bruno Guillon, Giovanni Pighizzini, Luca Prigioniero, Daniel Průša 

Publication date: 22 November 2018

Full work available at URL: https://doi.org/10.1007/978-3-319-98654-8_30

Recommendations

• Linear-time limited automata
• Linear-time limited automata
• Two-way finite automata: old and recent results
• Two-way finite automata: old and recent results
• A Time Complexity Gap for Two-Way Probabilistic Finite-State Automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cited In (5)

• Linear-time limited automata
• Converting nondeterministic two-way automata into small deterministic linear-time machines
• Weight-reducing Turing machines
• One-time nondeterministic computations
• One-time nondeterministic computations

This page was built for publication: Two-way automata and one-tape machines. Read only versus linear time

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