Biinfinite words with maximal recurrent unbordered factors

• Autor(es): Costa, José Carlos Cruz da
• Data: 2003
• Identificador Persistente: http://hdl.handle.net/1822/1808
• Origem: RepositóriUM - Universidade do Minho
• Assunto(s): Biinfinite word; Recurrent factor; Unbordered word; Ultimately periodic
• Tipo de Documento: Artigo
• Idioma: Inglês

Descrição

A finite non-empty word z is said to be a border of a finite non-empty word w if w=uz=zv for some non-empty words u and v. A finite non-empty word is said to be bordered if it admits a border, and it is said to be unbordered otherwise. In this paper, we give two characterizations of the biinfinite words of the form ...uuuvuuu..., where u and v are finite words, in terms of its unbordered factors. The main result of the paper states that the words of the form ...uuuvuuu... are precisely the biinfinite words w=...a_{-2}a_{-1}a_0a_1a_2... for which there exists a pair (l_0,r_0) of integers with l_0<r_0 such that, for every integers l\leq l_0 and r\geq r_0, the factor a_l...a_{l_0}...a_{r_0}... a_r is a bordered word. The words of the form ...uuuvuuu... are also characterized as being those biinfinite words w that admit a left recurrent unbordered factor (i.e., an unbordered factor of w that has an infinite number of occurrences "to the left'' in w) of maximal length that is also a right recurrent unbordered factor of maximal length. This last result is a biinfinite analogue of a result known for infinite words.