Roots and Powers in Regular Languages : Recognizing Nonregular Properties by Finite Automata

• Autorzy: Frei Fabian , Hromkovič Juraj , Karhumäki Juhani

Identyfikatory

DOI

10.3233/FI-2020-1952

• Języki publikacji: EN

Abstrakty

EN

It is well known that the set of powers of any given order, for example squares, in a regular language need not be regular. Nevertheless, finite automata can identify them via their roots. More precisely, we recall that, given a regular language L , the set of square roots of L is regular. The same holds true for the nth roots for any n and for the set of all nontrivial roots; we give a concrete construction for all of them. Using the above result, we obtain decision algorithms for many natural problems on powers. For example, it is decidable, given two regular languages, whether they contain the same number of squares at each length. Finally, we give an exponential lower bound on the size of automata identifying powers in regular languages. Moreover, we highlight interesting behavior differences between taking fractional powers of regular languages and taking prefixes of a fractional length. Indeed, fractional roots in a regular language can typically not be identified by finite automata.

Słowa kluczowe

EN

finite state machine; fractional power; concrete construction; language & languages

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2020
• Tom: Vol. 175, nr 1-4
• Strony: 173--185
• Opis fizyczny: Bibliogr. 12 poz., rys.

Twórcy

autor

Frei Fabian

• Department of Computer Science, ETH Zürich, Zürich, Switzerland

autor

Hromkovič Juraj

• Department of Computer Science, ETH Zürich, Zürich, Switzerland

autor

Karhumäki Juhani

• Department of Mathematics and Statistics, University of Turku, Turku, Finland

Bibliografia

• [1] Lischke G. The Root of a Language and Its Complexity. In: Kuich W, Rozenberg G, Salomaa A (eds.), Developments in Language Theory, 5th International Conference, volume 2295 of Lecture Notes in Computer Science. Springer, 2001 pp. 272-280. doi:10.1007/3-540-46011-X_23.
• [2] Hopcroft JE, Ullman JD. Introduction to Automata Theory, Languages and Computation. Addison-Wesley, 1979. ISBN:020102988X, 9780201029888.
• [3] Lothaire M. Combinatorics on words, Second Edition. Edited by M. Lothaire. Cambridge University Press, 1997. ISBN:9780521599245.
• [4] Maslov AN. Estimates of the number of states of finite automata. Doklady Akademii Nauk SSSR, 1970. 194:1266-1268. URL http://mi.mathnet.ru/eng/dan35742.
• [5] Caron P, le Court EH, Luque J, Patrou B. New tools for state complexity. Discrete Mathematics and Theoretical Computer Science, 2020. 22(1). arXiv:1807.00663 [cs.FL].
• [6] Sakarovitch J. Elements of Automata Theory. Cambridge University Press, 2009. ISBN:10: 0521844258, 13: 978-0521844253.
• [7] Shallit J. A second course in formal languages and automata theory. SIGACT News, 2010. 41(2):40-43. doi:10.1145/1814370.1814383.
• [8] Kosaraju SR. Regularity Preserving Functions. Technical Report JHU EE 74-2, John Hopkins University, Electrical Engineering Department, 1974. doi:10.1145/1008304.1008306.
• [9] Salomaa A, Soittola M. Automata-Theoretic Aspects of Formal Power Series. Texts and Monographs in Computer Science. Springer, 1978. doi:10.1007/978-1-4612-6264-0.
• [10] Eilenberg S. Automata, languages, and machines, volume A. Academic Press, 1974. ISBN:9780080873749.
• [11] Holzer M, König B. Regular Languages, Sizes of Syntactic Monoids, Graph Colouring, State Complexity Results, and How These Topics are Related to Each Other. Bulletin of the EATCS, 2004. 83:139-155. ID:17698902.
• [12] Krawetz B, Lawrence J, Shallit JO. State complexity and the monoid of transformations of a finite set. Int. J. of Foundations of Computer Science, 2005. 16(3):547-563. doi:10.1007/978-3-540-30500-2_20.

Uwagi

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