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

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