Article ID Journal Published Year Pages File Type
9657806 Theoretical Computer Science 2005 18 Pages PDF
Abstract
Smooth infinite words over Σ={1,2} are connected to the Kolakoski word K=221121⋯, defined as the fixpoint of the function Δ that counts the length of the runs of 1's and 2's. In this paper we extend the notion of smooth words to arbitrary alphabets and study some of their combinatorial properties. Using the run-length encoding Δ, every word is represented by a word obtained from the iterations of Δ. In particular we provide a new representation of the infinite Fibonacci word F as an eventually periodic word. On the other hand, the Thue-Morse word is represented by a finite one.
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , ,