TY - GEN

T1 - On the length of shortest strings accepted by two-way finite automata

AU - Dobronravov, Egor

AU - Dobronravov, Nikita

AU - Okhotin, Alexander

PY - 2019/1/1

Y1 - 2019/1/1

N2 - Given a two-way finite automaton recognizing a non-empty language, consider the length of the shortest string it accepts, and, for each n ≥ 1, let f(n) be the maximum of these lengths over all n-state automata. It is proved that for n-state two-way finite automata, whether deterministic or nondeterministic, this number is at least Ω(8n/5) and less than, with the lower bound reached over an alphabet of size Θ(n). Furthermore, for deterministic automata and for a fixed alphabet of size m ≥ 1, the length of the shortest string is at least (Formula Presented).

AB - Given a two-way finite automaton recognizing a non-empty language, consider the length of the shortest string it accepts, and, for each n ≥ 1, let f(n) be the maximum of these lengths over all n-state automata. It is proved that for n-state two-way finite automata, whether deterministic or nondeterministic, this number is at least Ω(8n/5) and less than, with the lower bound reached over an alphabet of size Θ(n). Furthermore, for deterministic automata and for a fixed alphabet of size m ≥ 1, the length of the shortest string is at least (Formula Presented).

UR - http://www.scopus.com/inward/record.url?scp=85073906465&partnerID=8YFLogxK

UR - http://www.mendeley.com/research/length-shortest-strings-accepted-twoway-finite-automata

U2 - 10.1007/978-3-030-24886-4_6

DO - 10.1007/978-3-030-24886-4_6

M3 - Conference contribution

AN - SCOPUS:85073906465

SN - 9783030248857

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 88

EP - 99

BT - Developments in Language Theory - 23rd International Conference, DLT 2019, Proceedings

A2 - Hofman, Piotrek

A2 - Skrzypczak, Michał

PB - Springer Nature

T2 - 23rd International Conference on Developments in Language Theory, DLT 2019

Y2 - 5 August 2019 through 9 August 2019

ER -