Equivalence Relations Defined by Numbers of Occurrences of Factors

• Autorzy: Saarela A.

Identyfikatory

DOI

10.3233/FI-2016-1367

• Języki publikacji: EN

Abstrakty

EN

We study the question of what can be said about a word based on the numbers of occurrences of certain factors in it. We do this by defining a family of equivalence relations that generalize the so called k-abelian equivalence. The characterizations and answers we obtain are linear algebraic. We also use these equivalence relations to help us in solving some problems related to repetitions and palindromes, and to point out that some previous results about Sturmian words and k-abelian equivalence hold in a more general form.

Słowa kluczowe

EN

equivalence relation; palindrome; problem solving; abelian equations; linear algebra

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2016
• Tom: Vol. 145, nr 3
• Strony: 385--397
• Opis fizyczny: Bibliogr. 15 poz.

Twórcy

autor

Saarela A.

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

Bibliografia

• [1] Karhumäki J. Generalized Parikhmappings and homomorphisms. Information and Control. 1980;47(3):155–165. doi:10.1016/S0019-9958(80)90493-3.
• [2] 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.
• [3] Cassaigne J, Karhumäki J, Saarela A. On growth and fluctuation of k-abelian complexity. In: Proceedings of the 10th CSR. vol. 9139 of LNCS. Springer; 2015. p. 109–122. doi:10.1007/978-3-319-20297-6 8.
• [4] Huova M, Karhumäki J, Saarela A, Saari K. Local squares, periodicity and finite automata. In: Calude C, Rozenberg G, Salomaa A, editors. Rainbow of Computer Science. vol. 6570 of LNCS. Springer; 2011. p. 90–101. doi:10.1007/978-3-642-19391-0 7.
• [5] Rao M. On some generalizations of abelian power avoidability. Theoret Comput Sci. 2015;601:39–46. doi:10.1016/j.tcs.2015.07.026.
• [6] Dekking M. Strongly nonrepetitive sequences and progression-free sets. J Combin Theory Ser A. 1979;27(2):181–185. doi:10.1016/0097-3165(79)90044-X.
• [7] Keränen V. Abelian squares are avoidable on 4 letters. In: Proceedings of the 19th ICALP. vol. 623 of LNCS. Springer; 1992. p. 41–52. doi:10.1007/3-540-55719-9 62.
• [8] HuovaM, Saarela A. Strongly k-abelian repetitions. In: Proceedings of the 9thWORDS. vol. 8079 of LNCS. Springer; 2013. p. 161–168. doi:10.1007/978-3-642-40579-2 18.
• [9] Huova M. Combinatorics on words. New aspects on avoidability, defect effect, equations and palindromes; 2014. Doctoral dissertation, University of Turku.
• [10] Karhumäki J, Puzynina S. On k-abelian palindromic rich and poor words. In: Proceedings of the 18th DLT. vol. 8633 of LNCS. Springer; 2014. p. 191–202. doi:10.1007/978-3-319-09698-8 17.
• [11] 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.
• [12] Parreau A, RigoM, Rowland E, Vandomme E. A new approach to the 2-regularity of the l-abelian complexity of 2-automatic sequences. Electron J Combin. 2015;22(1):P1.27.
• [13] Morse M, Hedlund GA. Symbolic dynamics. Amer J Math. 1938;60(4):815–866. doi:10.2307/2371264.
• [14] Morse M, Hedlund GA. Symbolic dynamics II: Sturmian trajectories. Amer J Math. 1940;62(1):1–42.
• [15] Coven EM, Hedlund GA. Sequences with minimal block growth. Math Systems Theory. 1973;7:138–153. doi:10.1007/BF01762232.

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).