Guibas and Odlyzko’s Theorem

In this chapter, we discuss a fundamental periodicity result on words due to Guibas and Odlyzko which states that for every word u, there exists a “binary equivalent for u,” that is, a binary word v of same length as u that has exactly the same set of periods as u. In summary, the following table describes the number of holes and section numbers where the above mentioned result is discussed:

0 5.1 1 5.2 and 5.3

In this section, we restrict ourselves to full words. We first state Guibas and Odlyzko’s result.