α-Words and factors of characteristic sequences

• Published in: Discrete mathematics 1997-12, Vol.177 (1), p.33-50
• Main Author: Chuan, Wai-Fong
• Format: Article
• Language: English
• ISSN: 0012-365X; 1872-681X
• DOI: 10.1016/S0012-365X(96)00355-X

Let α be an irrational number with 0 < α < 1. Using the continued fraction expansion of α, the class of α-words is introduced. It contains certain sequences of words that are known to relate to the characteristic sequence ƒ(α) of α. When α = (√5 − 1) 2 , α-words are precisely the Fibonacci words. In this paper, the class of α-words is shown to be a subset of factors of ƒ(α), which is closed under both conjugation and reversion. The canonical palindrome factorization of unbordered α-words play an important role in the determination of factors of ƒ(α). It is proved that every unbordered α-word w that we obtain determines a (| w| + 1) × | w| matrix C of the form C= circ(w) y such that for every 1 ⩽ k ⩽ | w|, the rows of the upper left ( k + 1) × k submatrix are distinct factors of ƒ(α) of length k. As a consequence of a well-known result, this actually gives all the factors of ƒ(α) of length k.