کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4952299 | 1364438 | 2017 | 15 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On cardinalities of k-abelian equivalence classes
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: On cardinalities of k-abelian equivalence classes On cardinalities of k-abelian equivalence classes](/preview/png/4952299.png)
چکیده انگلیسی
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), 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=2, the lower bound Ω(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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 658, Part A, 7 January 2017, Pages 190-204
Journal: Theoretical Computer Science - Volume 658, Part A, 7 January 2017, Pages 190-204
نویسندگان
Juhani Karhumäki, Svetlana Puzynina, Michaël Rao, Markus A. Whiteland,