Discrete Mathematics & Theoretical Computer Science, Vol 4, No 2 (2001)

Font Size:  Small  Medium  Large

Overlap-free symmetric D0L words

Anna Frid

Abstract


A D0L word on an alphabet Σ={0,1,…,q-1} is called symmetric if it is a fixed point w=φ(w) of a morphism φ:Σ* → Σ* defined by φ(i)=t1 + i t2 + i… tm + i for some word t1t2… tm (equal to φ(0)) and every i ∈ Σ; here a means a &bmod; q. We prove a result conjectured by J. Shallit: if all the symbols in φ(0) are distinct (i.e., if ti &neq; tj for i &neq; j), then the symmetric D0L word w is overlap-free, i.e., contains no factor of the form axaxa for any x ∈ Σ* and a ∈ Σ.

Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page