2018/04/27 by Costa, J. C., Nogueira, C., Teixeira, M. L.
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1804.10461
Given two finite words u and v of equal length, define the overlap gap between u and v, denoted og(u,v), as the least integer m for which there exist words x and x' of length m such that xu=vx' or ux=x'v. Informally, the overlap gap measures the outside parts of the greatest overlap of the given words. For a left-infinite word λ and a right-infinite word ρ, let ogλ,ρ be the function defined, for each non-negative integer n, by ogλ,ρ(n)=og(λn,ρn), where λn and ρn are, respectively, the suffix of λ and the prefix of ρ of length n. Also, denote by OGλ,ρ the image of the function ogλ,ρ. In this paper, we show that OGλ,ρ is a finite set if and only if λ and ρ are ultimately periodic infinite words of the form λ=u-∞w1=⋯ uuuw1 and ρ=w2u^∞=w2uuu⋯ for some finite words u, w1 and w2.