Harju, Tero, Lepistö, Arto and Nowotka, Dirk (2005) A characterization of periodicity of bi-infinite words. Theoretical Computer Science, 347 (1-2). pp. 419-422. DOI 10.1016/j.tcs.2004.08.017.

Preview

Text Biinfinite.pdf Download (93kB) | Preview

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.

Actions (login required)

View Item