Shortest accepted strings for two-way finite automata: approaching the \(2^n\) lower bound
From MaRDI portal
Publication:6175095
DOI10.1007/978-3-031-34326-1_10OpenAlexW4381855978MaRDI QIDQ6175095
Alexander Okhotin, Olga Martynova
Publication date: 17 August 2023
Published in: Descriptional Complexity of Formal Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-031-34326-1_10
Cites Work
- Unnamed Item
- Rational indexes of generators of the cone of context-free languages
- Longer shortest strings in two-way finite automata
- Deterministic one-way simulation of two-way deterministic finite automata over small alphabets
- Rational index of languages with bounded dimension of parse trees
- Reversibility of computations in graph-walking automata
- Shortest Paths in One-Counter Systems
- On the Length of Shortest Strings Accepted by Two-way Finite Automata
- Decidability and Shortest Strings in Formal Languages
- Mathematical Foundations of Computer Science 2005
This page was built for publication: Shortest accepted strings for two-way finite automata: approaching the \(2^n\) lower bound