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. We show that the set of lexicographically least representatives of equivalence classes is a regular language. From this we infer that the sequence of the numbers of equivalence classes is $$\\mathbb {N}$$-rational. We also show that the set of words defining k-abelian singleton classes is regular. |
Year | DOI | Venue |
---|---|---|
2017 | 10.3233/FI-2017-1553 | Fundam. Inform. |
Keywords | DocType | Volume |
k-abelian equivalence,Regular languages,Rational sequences | Journal | 154 |
Issue | ISSN | Citations |
1-4 | 0169-2968 | 2 |
PageRank | References | Authors |
0.41 | 7 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Julien Cassaigne | 1 | 282 | 40.80 |
Juhani Karhumäki | 2 | 1115 | 152.77 |
Svetlana Puzynina | 3 | 50 | 13.13 |
Markus Whiteland | 4 | 7 | 3.39 |