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

DOI10.1016/J.IC.2022.104938OpenAlexW3134046426WikidataQ114172424 ScholiaQ114172424MaRDI QIDQ2105419FDOQ2105419

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

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.

zbMATH Keywords

descriptional complexitytwo-way automataone-tape Turing machinesSakoda-Sipser conjecture

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

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

Cited In (2)

• Weight-reducing Turing machines
• Transforming Two-Way Alternating Finite Automata to One-Way Nondeterministic Automata

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)