Abstract

A finite word is called bordered if it has a proper prefix which is also a suffix of that word. Costa proves in [Theoret. Comput. Sci., 290(3):2053-2061, 2003] that a bi-infinite word w is of the form ^ωfgf^ω, for some finite words f and g, if, and only if, there is a factorization w = suv, where u is a finite word and every factor s'uv', where s' is a suffix of s and v' is a prefix of v, is bordered. We present a shorter proof of that result in this paper.

Keywords: combinatorics on words, bi-infinite words, unbordered factors, periodicity

Full paper: [ps - 715 KB] [ps.gz - 88 KB] [pdf - 92 KB].