Warianty tytułu
Języki publikacji
Abstrakty
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).
Słowa kluczowe
Czasopismo
Rocznik
Tom
Strony
315--331
Opis fizyczny
Bibliogr. 13 poz., rys., tab.
Twórcy
autor
- Department of Mathematics and Computer Science, St. Petersburg State University, 7/9 Universitetskaya nab., Saint Petersburg 199034, Russia, yegordobronravov@mail.ru
autor
- Department of Mathematics and Computer Science, St. Petersburg State University, 7/9 Universitetskaya nab., Saint Petersburg 199034, Russia, dobronravov1999@mail.ru
autor
- Department of Mathematics and Computer Science, St. Petersburg State University, 7/9 Universitetskaya nab., Saint Petersburg 199034, Russia, alexander.okhotin@spbu.ru
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).
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.baztech-6af85eff-eabc-42c4-a2e2-a09b609e5d5a