کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6875559 | 1441969 | 2018 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On semi-perfect de Bruijn words
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We show an application of Lempel's recursive construction of De Bruijn words to the generation of binary words having many factor-rich prefixes. A binary word is said to be factor-rich iff it has the largest number of distinct factors among binary words with the same length. A linear de Bruijn word of rank n is a shortest word containing (as a factor) exactly once each binary word of length n. It is factor-rich and its length equals În=2n+nâ1. We construct for each n a binary linear de Bruijn word of rank n which is semi-perfect in the following sense: each of its prefixes of length m>Înâ1 is factor-rich. The number Înâ1 is the best possible (for n>2 there is no linear binary de Bruijn word with factor-rich prefix of length m=Înâ1). We show an efficient algorithm constructing compact description of binary semi-perfect de Bruijn words.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 720, 11 April 2018, Pages 55-63
Journal: Theoretical Computer Science - Volume 720, 11 April 2018, Pages 55-63
نویسندگان
Damian Repke, Wojciech Rytter,