On the Size of Two-Way Reasonable Automata for the Liveness Problem
From MaRDI portal
Publication:4640037
DOI10.1142/S0129054118400038zbMath1387.68153OpenAlexW2797341324MaRDI QIDQ4640037
Ivan Kováč, Maria Paola Bianchi, Juraj Hromkovič
Publication date: 15 May 2018
Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1142/s0129054118400038
Cites Work
- Size complexity of rotating and sweeping automata
- Finite automata and unary languages
- Lower bounds on the size of sweeping automata
- Two-way deterministic finite automata are exponentially more succinct than sweeping automata
- Converting two-way nondeterministic unary automata into simpler automata.
- Nondeterminism is essential in small two-way finite automata with few reversals
- Magic numbers in the state hierarchy of finite automata
- Size Complexity of Two-Way Finite Automata
- Nondeterminism and the size of two way finite automata
- Mathematical Foundations of Computer Science 2005
- DETERMINISM VS. NONDETERMINISM FOR TWO-WAY AUTOMATA: Representing the Meaning of States by Logical Formulæ
- On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
