k-Abelian Equivalence and Rationality




Julien Cassaigne, Karhumäki Juhani, Puzynina Svetlana, Whiteland Markus

S. Brlek and C. Reutenauer

International Conference on Developments in Language Theory

Berlin

2016

Developments in Language Theory, 20th International Conference, DLT 2016

Lecture Notes in Computer Science

9840

77

88

12

978-3-662-53131-0

978-3-662-53132-7

0302-9743

DOIhttps://doi.org/10.1007/978-3-662-53132-7_7



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 $N$-rational. We
also show that the set of words defining $k$-abelian singleton classes is regular.


Last updated on 2024-26-11 at 16:18