A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
On cardinalities of k-abelian equivalence classes
Tekijät: Juhani Kahumäki, Svetlana Puzynina, Michaël Rao, Markus Whiteland
Kustantaja: Elsevier
Julkaisuvuosi: 2017
Lehti: Theoretical Computer Science
Vuosikerta: 658
Numero: Part A
Aloitussivu: 190
Lopetussivu: 204
Sivujen määrä: 15
ISSN: 0304-3975
DOI: https://doi.org/10.1016/j.tcs.2016.06.010
Verkko-osoite: http://dx.doi.org/10.1016/j.tcs.2016.06.010
Rinnakkaistallenteen osoite: https://research.utu.fi/converis/portal/detail/Publication/18254217
Tiivistelmä
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.
Avainsanat:
k-abelian equivalence
Ladattava julkaisu This is an electronic reprint of the original article. |  |
Turun yliopiston Tutkimustietojärjestelmän portaali