A1 Refereed original research article in a scientific journal
On cardinalities of k-abelian equivalence classes
Authors: Juhani Kahumäki, Svetlana Puzynina, Michaël Rao, Markus Whiteland
Publisher: Elsevier
Publication year: 2017
Journal: Theoretical Computer Science
Volume: 658
Issue: Part A
First page : 190
Last page: 204
Number of pages: 15
ISSN: 0304-3975
DOI: https://doi.org/10.1016/j.tcs.2016.06.010
Web address : http://dx.doi.org/10.1016/j.tcs.2016.06.010
Self-archived copy’s web address: https://research.utu.fi/converis/portal/detail/Publication/18254217
Abstract
Two words $u$ and $v$ are $k$-abelian equivalent if for each word $x$ of length at most $k$, $x$ occurs equally
many times as a factor in both $u$ and $v$. The notion of $k$-abelian equivalence is an intermediate notion between the abelian equivalence and the equality of words. In this paper, we study the equivalence classes induced by the $k$-abelian equivalence, mainly focusing on the cardinalities of the classes. In particular, we are interested in the number of singleton $k$-abelian classes, i.e., classes containing only one element. We find a connection between the
singleton classes and cycle decompositions of the de Bruijn graph. We show that the number of classes of words of length $n$ containing one single element is of order $mathcal O (n^{N_m(k-1)-1})$, where $N_m(l)= frac{1}{l}sum_{dmid l}arphi(d)m^{l/d}$ is the number of necklaces of length $l$ over an $m$-ary alphabet. We conjecture that the upper bound is sharp. We also remark that, for $k$ even and $m=2$, the lower bound $Omega (n^{N_m(k-1)-1})$
follows from an old conjecture on the existence of Gray codes for necklaces of odd length. We verify this conjecture for necklaces of length up to 15.
Two words $u$ and $v$ are $k$-abelian equivalent if for each word $x$ of length at most $k$, $x$ occurs equally
many times as a factor in both $u$ and $v$. The notion of $k$-abelian equivalence is an intermediate notion between the abelian equivalence and the equality of words. In this paper, we study the equivalence classes induced by the $k$-abelian equivalence, mainly focusing on the cardinalities of the classes. In particular, we are interested in the number of singleton $k$-abelian classes, i.e., classes containing only one element. We find a connection between the
singleton classes and cycle decompositions of the de Bruijn graph. We show that the number of classes of words of length $n$ containing one single element is of order $mathcal O (n^{N_m(k-1)-1})$, where $N_m(l)= frac{1}{l}sum_{dmid l}arphi(d)m^{l/d}$ is the number of necklaces of length $l$ over an $m$-ary alphabet. We conjecture that the upper bound is sharp. We also remark that, for $k$ even and $m=2$, the lower bound $Omega (n^{N_m(k-1)-1})$
follows from an old conjecture on the existence of Gray codes for necklaces of odd length. We verify this conjecture for necklaces of length up to 15.
Downloadable publication This is an electronic reprint of the original article. |  |
UTU Research Portal