کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4646952 | 1342320 | 2015 | 12 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Generalized de Bruijn words for primitive words and powers
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We show that for every n≥1n≥1 and over any finite alphabet, there is a word whose circular factors of length nn have a one-to-one correspondence with the set of primitive words. In particular, we prove that such a word can be obtained by a greedy algorithm, or by concatenating all Lyndon words of length nn in increasing lexicographic order. We also look into connections between de Bruijn graphs of primitive words and Lyndon graphs.Finally, we also show that the shortest word that contains every pp-power of length pnpn over a kk-letter alphabet has length between pknpkn and roughly (p+1k)kn, for all integers p≥1p≥1. An algorithm that generates a word which achieves the upper bound is provided.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 338, Issue 12, 6 December 2015, Pages 2320–2331
Journal: Discrete Mathematics - Volume 338, Issue 12, 6 December 2015, Pages 2320–2331
نویسندگان
Yu Hin Au,