کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
437183 | 690086 | 2006 | 12 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Combinatorial properties of smooth infinite words
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
We describe some combinatorial properties of an intriguing class of infinite words, called smooth, connected with the Kolakoski one, K, defined as the fixed point of the run-length encoding Δ. It is based on a bijection on the free monoid over Σ={1,2}, that shows some surprising mixing properties. All words contain the same finite number of square factors, and consequently they are cube-free. This suggests that they have the same complexity as confirmed by extensive computations. We further investigate the occurrences of palindromic subwords. Finally, we show that there exist smooth words obtained as fixed points of substitutions (realized by transducers) as in the case of K.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 352, Issues 1–3, 7 March 2006, Pages 306-317
Journal: Theoretical Computer Science - Volume 352, Issues 1–3, 7 March 2006, Pages 306-317