Shortest accepted strings for two-way finite automata: approaching the 2ⁿ lower bound

DOI10.1007/978-3-031-34326-1_10MaRDI QIDQ6175095zbMATH OpenOpenAlexFDO

Authors Olga Martynova, Alexander Okhotin

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

• Decidability and shortest strings in formal languages
• Deterministic one-way simulation of two-way deterministic finite automata over small alphabets
• Longer shortest strings in two-way finite automata
• Mathematical Foundations of Computer Science 2005
• On the length of shortest strings accepted by two-way finite automata
• Rational index of languages with bounded dimension of parse trees
• Rational indexes of generators of the cone of context-free languages
• Regular expressions: new results and open problems
• Reversibility of computations in graph-walking automata

Cited in

(1)

• Rational index of languages defined by grammars with bounded dimension of parse trees

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6175095)