Converting nondeterministic two-way automata into small deterministic linear-time machines

DOI10.1016/J.IC.2022.104938MaRDI QIDQ2105419zbMATH OpenOpenAlexWikidataFDO

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

Publication date 8 December 2022

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2103.05485

zbMATH Keywords

descriptional complexityone-tape Turing machinesSakoda-Sipser conjecturetwo-way automata

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Two-way automata and one-tape machines. Read only versus linear time
• Two-way finite automata: old and recent results
• scientific article; zbMATH DE number 1848284
• Converting two-way nondeterministic unary automata into simpler automata.

Cites work

• An NP-complete language accepted in linear time by a one-tape Turing machine
• Classes of languages and linear-bounded automata
• Computational Complexity of One-Tape Turing Machine Computations
• Converting two-way nondeterministic unary automata into simpler automata.
• Deterministic context-sensitive languages: Part II
• scientific article; zbMATH DE number 3936519 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 2038729 (Why is no real title available?)
• scientific article; zbMATH DE number 7354705 (Why is no real title available?)
• scientific article; zbMATH DE number 5593330 (Why is no real title available?)
• scientific article; zbMATH DE number 3254906 (Why is no real title available?)
• scientific article; zbMATH DE number 3319549 (Why is no real title available?)
• Limited automata and regular languages
• Limited automata and unary languages
• Lower bounds on the size of sweeping automata
• More concise representation of regular languages by automata and regular expressions
• Non-self-embedding grammars, constant-height pushdown automata, and limited automata
• Nondeterminism and the size of two way finite automata
• Nondeterminism is essential in small two-way finite automata with few reversals
• One-tape, off-line Turing machine computations
• Relationships between nondeterministic and deterministic tape complexities
• Theory of one-tape linear-time Turing machines
• Two-way automata and one-tape machines. Read only versus linear time
• Two-way automata characterizations of L/poly versus NL
• Two-way automata versus logarithmic space
• Two-way finite automata: old and recent results
• Weight-reducing Hennie machines and their descriptional complexity

Cited in

(3)

• Transforming Two-Way Alternating Finite Automata to One-Way Nondeterministic Automata
• Weight-reducing Turing machines
• Two-way automata and bounded languages

This page was built for publication: Converting nondeterministic two-way automata into small deterministic linear-time machines

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