Equivalence Relations Defined by Numbers of Occurrences of Factors

Issue title: Discrete Mathematics (RuFiDiM 14)

Guest editors: J. Karhumäki, V. Mazalov and Yu. Matiyasevich

Article type: Research Article

Authors: Saarela, Aleksi^{*; †}

Affiliations: Department of Mathematics and Statistics, University of Turku, 20014 Turku, Finland. amsaar@utu.fi

Correspondence: [*] Address for correspondence: Department of Mathematics and Statistics, University of Turku, 20014 Turku, Finland

Note: [†] Supported by the Academy of Finland under grant 137991

Abstract: 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.

DOI: 10.3233/FI-2016-1367

Journal: Fundamenta Informaticae, vol. 145, no. 3, pp. 385-397, 2016