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

• Autorzy: Dobronravov Egor , Dobronravov Nikita , Okhotin Alexander

Identyfikatory

DOI

10.3233/FI-2021-2044

• Języki publikacji: EN

Abstrakty

EN

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 Ω(10^n/5) and less than (²ⁿ_n+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).

Słowa kluczowe

EN

finite automata; two-way automata; state complexity; shortest string

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2021
• Tom: Vol. 180, nr 4
• Strony: 315--331
• Opis fizyczny: Bibliogr. 13 poz., rys., tab.

Twórcy

autor

Dobronravov Egor

• Department of Mathematics and Computer Science, St. Petersburg State University, 7/9 Universitetskaya nab., Saint Petersburg 199034, Russia

autor

Dobronravov Nikita

• Department of Mathematics and Computer Science, St. Petersburg State University, 7/9 Universitetskaya nab., Saint Petersburg 199034, Russia

autor

Okhotin Alexander

• Department of Mathematics and Computer Science, St. Petersburg State University, 7/9 Universitetskaya nab., Saint Petersburg 199034, Russia

Bibliografia

• [1] L. Alpoge, Th. Ang, L. Schaeffer, J. Shallit, “Decidability and shortest strings in formal languages”, Descriptional Complexity of Formal Systems (DCFS 2011, Limburg, Germany, 25-27 July 2011), LNCS 6808, 2011 pp. 55-67. doi:10.1007/978-3-642-22600-7_5.
• [2] D. Chistikov, W. Czerwinski, P. Hofman, M. Pilipczuk, M. Wehar, “Shortest paths in one-counter systems”, FoSSaCS 2016: Foundations of Software Science and Computation Structures, LNCS 9634, 2016 pp. 462-478. doi:10.1007/978-3-662-49630-5_27.
• [3] M. Chrobak, “Finite automata and unary languages”, Theoretical Computer Science, 47 (1986), 149-158. Errata: 2003. 302:497-498. doi:10.1016/0304-3975(86)90142-8.
• [4] E. Dobronravov, N. Dobronravov, A. Okhotin, “On the length of shortest strings accepted by two-way finite automata”, Developments in Language Theory (DLT 2019, Warsaw, Poland, 5-9 August 2019), LNCS 11647, 2019 pp. 88-99. doi:10.1007/978-3-030-24886-4_6.
• [5] K. Ellul, B. Krawetz, J. Shallit, M.-w. Wang, “Regular expressions: new results and open problems”, Journal of Automata, Languages and Combinatorics, 2005. 10(4):407-437. doi:10.25596/jalc-2005-407.
• [6] V. Geffert, C. Mereghetti, G. Pighizzini, “Converting two-way nondeterministic unary automata into simpler automata”, Theoretical Computer Science, 2003. 295(1-3):189-203. doi:10.1016/S0304-3975(02)00403-6.
• [7] V. Geffert, A. Okhotin, “One-way simulation of two-way finite automata over small alphabets”, NCMA 2013 (Umeå, Sweden, 13-14 August 2013). 2013. 294:151-162.
• [8] C. A. Kapoutsis, “Removing bidirectionality from nondeterministic finite automata”, Mathematical Foundations of Computer Science (MFCS 2005, Gdansk, Poland, 29 August-2 September 2005), LNCS 3618, 2005 pp. 544-555. doi:10.1007/11549345_47.
• [9] M. Kunc, A. Okhotin, “Describing periodicity in two-way deterministic finite automata using transformation semigroups”, Developments in Language Theory (DLT 2011, Milan, Italy, 19-22 July 2011), LNCS 6795, 2011 pp. 324-336. doi:10.1007/978-3-642-22321-1_28.
• [10] M. Kunc, A. Okhotin, “Reversibility of computations in graph-walking automata”, Information and Computation, 2020. 275:104631. doi:10.1016/j.ic.2020.104631.
• [11] E. Landau, “Über die Maximalordnung der Permutationen gegebenen Grades” (On the maximal order of permutations of a given degree), Archiv der Mathematik und Physik, Ser. 3, 1903. 5:92-103.
• [12] L. Pierre, “Rational indexes of generators of the cone of context-free languages”, Theoretical Computer Science, 1992. 95(2):279-305. doi:10.1016/0304-3975(92)90269-L.
• [13] M. Sipser, “Lower bounds on the size of sweeping automata”, STOC 1979, 1979 pp. 360-364. doi:10.1145/800135.804429.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2021).