Converting nondeterministic two-way automata into small deterministic linear-time machines
From MaRDI portal
Publication:2105419
DOI10.1016/j.ic.2022.104938OpenAlexW3134046426WikidataQ114172424 ScholiaQ114172424MaRDI QIDQ2105419
Giovanni Pighizzini, Luca Prigioniero, Daniel Průša, Bruno Guillon
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
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Two-way automata making choices only at the endmarkers
- More concise representation of regular languages by automata and regular expressions
- Theory of one-tape linear-time Turing machines
- Lower bounds on the size of sweeping automata
- An NP-complete language accepted in linear time by a one-tape Turing machine
- Converting two-way nondeterministic unary automata into simpler automata.
- Two-way automata and one-tape machines - read only versus linear time
- Nondeterminism is essential in small two-way finite automata with few reversals
- Two-way automata versus logarithmic space
- Two-way automata characterizations of L/poly versus NL
- Relationships between nondeterministic and deterministic tape complexities
- LIMITED AUTOMATA AND REGULAR LANGUAGES
- Nondeterminism and the size of two way finite automata
- Weight-Reducing Hennie Machines and Their Descriptional Complexity
- Computational Complexity of One-Tape Turing Machine Computations
- Deterministic context-sensitive languages: Part II
- Classes of languages and linear-bounded automata
- One-tape, off-line Turing machine computations
- Non-Self-Embedding Grammars, Constant-Height Pushdown Automata, and Limited Automata
- Limited automata and unary languages
This page was built for publication: Converting nondeterministic two-way automata into small deterministic linear-time machines
