Separating the Words of a Language by Counting Factors

• Autorzy: Saarela Aleksi

Identyfikatory

DOI

10.3233/FI-2021-2047

• Języki publikacji: EN

Abstrakty

EN

For a given language L, we study the languages X such that for all distinct words u, v ∈ L, there exists a word x ∈ X that appears a different number of times as a factor in u and in v. In particular, we are interested in the following question: For which languages L does there exist a finite language X satisfying the above condition? We answer this question for all regular languages and for all sets of factors of infinite words.

Słowa kluczowe

EN

combinatorics on words; k-abelian equivalence; regular language; infinite word

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2021
• Tom: Vol. 180, nr 4
• Strony: 375--393
• Opis fizyczny: Bibliogr. 19 poz.

Twórcy

autor

Saarela Aleksi

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

Bibliografia

• [1] Goralčík P, Koubek V. On discerning words by automata. In: Proceedings of the 13th ICALP, volume 226 of LNCS. Springer, 1986 pp. 116-122. doi:10.1007/3-540-16761-7\_61.
• [2] Robson JM. Separating strings with small automata. Inform. Process. Lett., 1989. 30(4):209-214. doi:10.1016/0020-0190(89)90215-9.
• [3] Demaine ED, Eisenstat S, Shallit J, Wilson DA. Remarks on separating words. In: Proceedings of the 13th DCFS, volume 6808 of LNCS. Springer, 2011 pp. 147-157. doi:10.1007/978-3-642-22600-7\_12.
• [4] Currie J, Petersen H, Robson JM, Shallit J. Separating words with small grammars. J. Autom. Lang. Comb., 1999. 4(2):101-110.
• [5] Place T, Zeitoun M. Separating regular languages with first-order logic. Log. Methods Comput. Sci., 2016. 12(1): Paper No. 5, 31. doi:10.2168/LMCS-12(1:5)2016.
• [6] Holub V, Kortelainen J. On partitions separating words. Internat. J. Algebra Comput., 2011. 21(8):1305-1316. doi:10.1142/S0218196711006650.
• [7] Maňuch J. Characterization of a word by its subwords. In: Proceedings of the 4th DLT. World Sci. Publ., 2000 pp. 210-219. doi:10.1142/9789812792464\_0018.
• [8] Vyalyĭ MN, Gimadeev RA. On separating words by the occurrences of subwords. Diskretn. Anal. Issled. Oper., 2014. 21(1):3-14. doi:10.1134/S1990478914020161.
• [9] Karhumäki J. Generalized Parikh mappings and homomorphisms. Information and Control, 1980. 47(3):155-165. doi:10.1016/S0019-9958(80)90493-3.
• [10] Karhumäki J, Saarela A, Zamboni LQ. On a generalization of Abelian equivalence and complexity of infinite words. J. Combin. Theory Ser. A, 2013. 120(8):2189-2206. doi:10.1016/j.jcta.2013.08.008.
• [11] Cassaigne J, Karhumäki J, Saarela A. On growth and fluctuation of k-abelian complexity. European J. Combin., 2017. 65:92-105. doi:10.1016/j.ejc.2017.05.006.
• [12] Chen J, Lü X, Wu W. On the k-abelian complexity of the Cantor sequence. J. Combin. Theory Ser. A, 2018. 155:287-303. doi:10.1016/j.jcta.2017.11.010.
• [13] Karhumäki J, Saarela A, Zamboni LQ. Variations of the Morse-Hedlund theorem for k-abelian equivalence. Acta Cybernet., 2017. 23(1):175-189. doi:10.14232/actacyb.23.1.2017.11.
• [14] Richomme G, Saari K, Zamboni LQ. Abelian complexity of minimal subshifts. J. Lond. Math. Soc. (2), 2011. 83(1):79-95. doi:10.1112/jlms/jdq063.
• [15] Cassaigne J, Karhumäki J, Puzynina S, Whiteland MA. k-abelian equivalence and rationality. Fund. Inform., 2017. 154(1-4):65-94. doi:10.3233/FI-2017-1553.
• [16] Saarela A. Separating many words by counting occurrences of factors. In: Proceedings of the 23rd DLT, volume 11647 of LNCS. Springer, 2019 pp. 251-264. doi:10.1007/978-3-030-24886-4_19.
• [17] Fine NJ, Wilf HS. Uniqueness theorems for periodic functions. Proc. Amer. Math. Soc., 1965. 16:109-114. doi:10.1090/S0002-9939-1965-0174934-9.
• [18] Morse M, Hedlund GA. Symbolic dynamics. Amer. J. Math., 1938. 60(4):815-866. doi:10.2307/2371264.
• [19] Ginsburg S, Spanier EH. Bounded regular sets. Proc. Amer. Math. Soc., 1966. 17:1043-1049. doi:10.2307/2036087.

Uwagi

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