Discrete Mathematics & Theoretical Computer Science, Vol 5 (2002)

Font Size:  Small  Medium  Large

Lyndon factorization of generalized words of Thue

Anton Černý


The i-th symbol of the well-known infinite word of Thue on the alphabet { 0,1} can be characterized as the parity of the number of occurrences of the digit 1 in the binary notation of i. Generalized words of Thue are based on counting the parity of occurrences of an arbitrary word w∈{ 0,1}+-0* in the binary notation of i. We provide here the standard Lyndon factorization of some subclasses of this class of infinite words.

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