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 \emphKMP. 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.

Source : oai:HAL:hal-00958962v1

Volume: Vol. 4 no. 2

Published on: January 1, 2001

Submitted on: March 26, 2015

Keywords: defect effect,bi-infinite words,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

This page has been seen 90 times.

This article's PDF has been downloaded 95 times.