Research output: Contribution to journal › Article › peer-review
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.
| Original language | English |
|---|---|
| Pages (from-to) | 65-94 |
| Number of pages | 30 |
| Journal | Fundamenta Informaticae |
| Volume | 154 |
| Issue number | 1-4 |
| DOIs | |
| State | Published - 1 Jan 2017 |
ID: 35281155