id: 05264272
dt: j
an: 05264272
au: Brlek, S.; Jamet, D.; Paquin, G.
ti: Smooth words on 2-letter alphabets having same parity.
so: Theor. Comput. Sci. 393, No. 1-3, 166-181 (2008).
py: 2008
pu: Elsevier Science Publishers, Amsterdam
la: EN
cc: 
ut: smooth words; Kolakoski word; Lyndon factorization; letter frequency
ci: 
li: doi:10.1016/j.tcs.2007.11.019
ab: Summary: We consider smooth words over 2-letter alphabets $\{a,b\}$, where
    $a,b$ are integers having same parity, with $0<a<b$. We show that all
    are recurrent and that the closure of the set of factors under reversal
    holds for odd alphabets only. We provide a linear time algorithm
    computing the extremal words, with respect to lexicographic order. The
    minimal word is an infinite Lyndon word if and only if either $a=1$ and
    $b$ are odd, or $a,b$ are even. A connection is established between
    generalized Kolakoski words and maximal infinite smooth words over even
    2-letter alphabets revealing new properties for some of the generalized
    Kolakoski words. Finally, the frequency of letters in extremal words is
    1/2 for even alphabets, and for $a=1$ with $b$ odd, the frequency of
    $b$’s is $1/(\sqrt{2b-1} +1)$.
rv: