The overlap gap between left-infinite and right-infinite words

Abstract

We study ultimate periodicity properties related to overlaps between the suffixes of a left-infinite word λ and the prefixes of a right-infinite word ρ. The main theorem states that the set of minimum lengths of words x and x' such that xλ_n =ρ_n x' or λ_n x=x'ρ_n is finite, where n runs over positive integers and λ_n and ρ_n are respectively the suffix of λ and the prefix of ρ of length n, if and only if λ and ρ are ultimately periodic words of the form λ=...uuv and ρ=wuu... for some finite words u, v and w.