k-Abelian Equivalence and Rationality
Whiteland Markus; Karhumäki Juhani; Julien Cassaigne; Puzynina Svetlana
k-Abelian Equivalence and Rationality
Whiteland Markus
Karhumäki Juhani
Julien Cassaigne
Puzynina Svetlana
Julkaisun pysyvä osoite on:
https://urn.fi/URN:NBN:fi-fe2021042716240
https://urn.fi/URN:NBN:fi-fe2021042716240
Tiivistelmä
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.
Kokoelmat
- Rinnakkaistallenteet [19207]