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

DOI10.1007/978-3-319-98654-8_30MaRDI QIDQ1622984zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

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

Cited in

(5)

• Converting nondeterministic two-way automata into small deterministic linear-time machines
• Linear-time limited automata
• 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)