Shortest accepted strings for two-way finite automata: approaching the \(2^n\) lower bound

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

Mathematics Subject Classification ID

Theory of computing (68Qxx)

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