Tero Harju and Dirk Nowotka
Periods in Word Extensions


Acta Informatica, 43(3):165-171, 2006.

Abstract

Let π(w) denote the minimum period of the word w, let w be a primitive word with period π(w)<|w|, and let z be a prefix of w. It is shown that if π(wz)=π(w), then |z|<π(w)-gcd(|w|,|z|). Detailed improvements of this result are also proven. Finally, we show that each primitive word w has a conjugate w'=vu, where w=uv, such that π(w')=|w'| and |u|<π(w). As a corollary we give a short proof of the fact that if u, v, w are words such that u2 is a prefix of v2, and v2 is a prefix of w2, and v is primitive, then |w|>2|u|.

Keywords: combinatorics on words, periods

Full paper: [ps - 241 KB] [ps.gz - 111 KB] [pdf - 136 KB].