k-Abelian Equivalence and Rationality

k-Abelian Equivalence and Rationality Full article

Journal

Fundamenta Informaticae
ISSN: 0169-2968

Output data

Year: 2017, Volume: 154, Number: 1-4, Pages: 65-94 Pages count : 30 DOI: 10.3233/FI-2017-1553

Tags

k-abelian equivalence; Rational sequences; Regular languages

Authors

Cassaigne Julien ¹ , Karhumäki Juhani ² , Puzynina Svetlana ^3,4 , Whiteland Markus A. ²

Affiliations

1	Institut de Mathématiques de Marseille
2	Department of Mathematics and Statistics, University of Turku
3	Sobolev Institute of Mathematics
4	St. Petersburg State University

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.

Cassaigne J. , Karhumäki J. , Puzynina S. , Whiteland M.A.
k-Abelian Equivalence and Rationality
Fundamenta Informaticae. 2017. V.154. N1-4. P.65-94. DOI: 10.3233/FI-2017-1553 WOS Scopus OpenAlex

≡ Web of science:	WOS:000411027800007
≡ Scopus:	2-s2.0-85027340559
≡ OpenAlex:	W2744157486