Paper Info
Title
Biinfinite words with maximal recurrent unbordered factors
Abstract
A finite non-empty word z is said to be a border of a finite non-empty word w if w = uz = zυ for some non-empty words u and υ. 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 ωuυuω, where u and υ are finite words, in terms of its unbordered factors.The main result of the paper states that the words of the form ωuυuω are precisely the biinfinite words w=...a-2a-1a0a1a2... for which there exists a pair (l0, r0) of integers with l0 r0 such that, for every integers l ≤ l0 and r ≥ r0, the factor al... al0...ar0...ar is a bordered word.The words of the form ωuυuω 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.
Year
DOI
Venue
2003
10.1016/S0304-3975(02)00372-9
Theor. Comput. Sci.
Keywords
DocType
Volume
biinfinite words w,finite non-empty word,maximal length,maximal recurrent unbordered factor,Recurrent factor,finite non-empty word w,unbordered factor,Ultimately periodic,left recurrent unbordered factor,biinfinite analogue,Biinfinite word,biinfinite word,non-empty words u,Unbordered word,right recurrent unbordered factor
Journal
290
Issue
ISSN
Citations 
3
Theoretical Computer Science
5
PageRank 
References 
Authors
0.84
2
1
Name
Order
Citations
PageRank
José Carlos Costa1174.57