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

Font Size:  Small  Medium  Large

Defect Effect of Bi-infinite Words in the Two-element Case

Ján Maňuch

Abstract


Let X be a two-element set of words over a finite alphabet. If a bi-infinite word possesses two X-factorizations which are not shiftequivalent, then the primitive roots of the words in X are conjugates. Note, that this is a strict sharpening of a defect theorem for bi-infinite words stated in KMP. Moreover, we prove that there is at most one bi-infinite word possessing two different X-factorizations and give a necessary and sufficient conditions on X for the existence of such a word. Finally, we prove that the family of sets X for which such a word exists is parameterizable.

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