On the Length of Shortest Strings Accepted by Two-way Finite Automata

Issue title: Developments in Language Theory (DLT 2019)

Guest editors: Michał Skrzypczak and Piotr Hofman

Article type: Research Article

Authors: Dobronravov, Egor^{; *} | Dobronravov, Nikita | Okhotin, Alexander^{; †}

Affiliations: Department of Mathematics and Computer Science, St. Petersburg State University, 7/9 Universitetskaya nab., Saint Petersburg 199034, Russia. yegordobronravov@mail.ru, dobronravov1999@mail.ru, alexander.okhotin@spbu.ru

Correspondence: [*] Address for correspondence: Department of Mathematics and Computer Science, St. Petersburg State University, 7/9 Universitetskaya nab., Saint Petersburg 199034, Russia

Note: [†] Research supported by Russian Science Foundation, project 18-11-00100.

Abstract: 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 Ω(10n/5) and less than (2nn+1), 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 e(1+o(1))mn(log n− log m).

Keywords: Finite automata, two-way automata, state complexity, shortest string

DOI: 10.3233/FI-2021-2044

Journal: Fundamenta Informaticae, vol. 180, no. 4, pp. 315-331, 2021