dc.contributor.author | Michaël Rao | |
dc.contributor.author | Juhani Kahumäki | |
dc.contributor.author | Markus Whiteland | |
dc.contributor.author | Svetlana Puzynina | |
dc.date.accessioned | 2022-10-27T11:54:20Z | |
dc.date.available | 2022-10-27T11:54:20Z | |
dc.identifier.uri | https://www.utupub.fi/handle/10024/155801 | |
dc.description.abstract | Two words $u$ and $v$ are $k$-abelian equivalent if for each word $x$ of length at most $k$, $x$ occurs equally<br />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<br />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})$<br />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. | |
dc.language.iso | en | |
dc.publisher | Elsevier | |
dc.title | On cardinalities of k-abelian equivalence classes | |
dc.identifier.url | http://dx.doi.org/10.1016/j.tcs.2016.06.010 | |
dc.identifier.urn | URN:NBN:fi-fe2021042716238 | |
dc.relation.volume | 658 | |
dc.contributor.organization | fi=matematiikka|en=Mathematics| | |
dc.contributor.organization-code | 2606101 | |
dc.converis.publication-id | 18254217 | |
dc.converis.url | https://research.utu.fi/converis/portal/Publication/18254217 | |
dc.format.pagerange | 190 | |
dc.format.pagerange | 204 | |
dc.identifier.jour-issn | 0304-3975 | |
dc.okm.affiliatedauthor | Whiteland, Markus | |
dc.okm.affiliatedauthor | Puzynina, Svetlana | |
dc.okm.affiliatedauthor | Karhumäki, Juhani | |
dc.okm.discipline | 111 Matematiikka | fi_FI |
dc.okm.discipline | 113 Computer and information sciences | en_GB |
dc.okm.discipline | 113 Tietojenkäsittely ja informaatiotieteet | fi_FI |
dc.okm.discipline | 111 Mathematics | en_GB |
dc.okm.internationalcopublication | international co-publication | |
dc.okm.internationality | International publication | |
dc.okm.type | Journal article | |
dc.relation.doi | 10.1016/j.tcs.2016.06.010 | |
dc.relation.ispartofjournal | Theoretical Computer Science | |
dc.relation.issue | Part A | |
dc.year.issued | 2017 | |