A characterization of periodicity of bi-infinite words

: Harju T, Lepisto A, Nowotka D

Publisher: ELSEVIER SCIENCE BV

: 2005

Theoretical Computer Science

THEORETICAL COMPUTER SCIENCE

: THEOR COMPUT SCI

: 347

: 1-2

: 419

: 422

: 4

: 0304-3975

DOI: https://doi.org/10.1016/j.tcs.2004.08.017

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) (2003) 2053-2061] that a bi-infinite word w is of the form (omega)fgf(omega), for some finite words f and g, if, and only if, there is a factorization w = suv, with u epsilon A* such that every factor s'uv', with s' <= s and v' <= v, is bordered. We present a shorter proof of that result in this paper. (c) 2005 Elsevier B.V. All rights reserved.

Mathematics