Näytä suppeat kuvailutiedot

On cardinalities of k-abelian equivalence classes

Michaël Rao; Juhani Kahumäki; Markus Whiteland; Svetlana Puzynina

dc.contributor.authorMichaël Rao
dc.contributor.authorJuhani Kahumäki
dc.contributor.authorMarkus Whiteland
dc.contributor.authorSvetlana Puzynina
dc.date.accessioned2022-10-27T11:54:20Z
dc.date.available2022-10-27T11:54:20Z
dc.identifier.urihttps://www.utupub.fi/handle/10024/155801
dc.description.abstractTwo 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.isoen
dc.publisherElsevier
dc.titleOn cardinalities of k-abelian equivalence classes
dc.identifier.urlhttp://dx.doi.org/10.1016/j.tcs.2016.06.010
dc.identifier.urnURN:NBN:fi-fe2021042716238
dc.relation.volume658
dc.contributor.organizationfi=matematiikka|en=Mathematics|
dc.contributor.organization-code2606101
dc.converis.publication-id18254217
dc.converis.urlhttps://research.utu.fi/converis/portal/Publication/18254217
dc.format.pagerange190
dc.format.pagerange204
dc.identifier.jour-issn0304-3975
dc.okm.affiliatedauthorWhiteland, Markus
dc.okm.affiliatedauthorPuzynina, Svetlana
dc.okm.affiliatedauthorKarhumäki, Juhani
dc.okm.discipline111 Matematiikkafi_FI
dc.okm.discipline113 Computer and information sciencesen_GB
dc.okm.discipline113 Tietojenkäsittely ja informaatiotieteetfi_FI
dc.okm.discipline111 Mathematicsen_GB
dc.okm.internationalcopublicationinternational co-publication
dc.okm.internationalityInternational publication
dc.okm.typeJournal article
dc.relation.doi10.1016/j.tcs.2016.06.010
dc.relation.ispartofjournalTheoretical Computer Science
dc.relation.issuePart A
dc.year.issued2017


Aineistoon kuuluvat tiedostot

Thumbnail

Aineisto kuuluu seuraaviin kokoelmiin

Näytä suppeat kuvailutiedot