Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
437183 | Theoretical Computer Science | 2006 | 12 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics