On cardinalities of k-abelian equivalence classes

详细信息    查看全文

• 作者：Juhani Karhumä ; ki^a ; ^{karhumak@utu.fi} ; Svetlana Puzynina^b ; ^c ; ^d ; ^{s.puzynina@gmail.com} ; Michaë ; l Rao^b ; ^d ; ^{michael.rao@ens-lyon.fr} ; Markus A. Whiteland^a ; ^{mawhit@utu.fi}
• 关键词：k-abelian equivalence ; de Bruijn graph ; Necklaces ; Gray codes ; Hamiltonian paths
• 刊名：Theoretical Computer Science
• 出版年：2017
• 出版时间：7 January 2017
• 年：2017
• 卷：658
• 期：part_PA
• 页码：190-204
• 全文大小：468 K
• 卷排序：658

文摘

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 O(nNm(k−1)−1)O(nNm(k−1)−1), where Nm(l)=1l∑d|lφ(d)ml/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=2m=2, the lower bound Ω(nNm(k−1)−1)Ω(nNm(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.