Affiliations: [a] Institut de mathématiques de Marseille, case 907, 163 avenue de Luminy, 13288 Marseille Ceder 9, France. [email protected] | [b] Department of Mathematics and Statistics, University of Turku, 20014 University of Turku, Finland. [email protected] | [c] St. Petersburg State University, 14th Line V.O., 29B, Saint Petersburg 199178, Russia; Sobolev Institute of Mathematics, Russia. [email protected] | [d] Department of Mathematics and Statistics, University of Turku, 20014 University of Turku, Finland. [email protected]
Correspondence:
[‡]
Address for correspondence: Department of Mathematics and Statistics, University of Turku, 20014 University of Turku, Finland
Note: [*] Partially supported by the Academy of Finland, grant 257857.
Note: [†] Partially supported by the Vilho, Yrjö and Kalle Väisälä Foundation of the Finnish Academy of Science and Letters.
Abstract: Two words u and v are said to be k-abelian equivalent if, for each word x of length at most k, the number of occurrences of x as a factor of u is the same as for v. We study some combinatorial properties of k-abelian equivalence classes. Our starting point is a characterization of k-abelian equivalence by rewriting, so-called k-switching. Using this characterization we show that, over any fixed alphabet, the language of lexicographically least representatives of k-abelian equivalence classes is a regular language. From this we infer that the sequence of the numbers of equivalence classes is ℕ-rational. Furthermore, we show that the above sequence is asymptotically equal to a certain polynomial depending on k and the alphabet size.
