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

Abstract

Given two finite words $u$ and $v$ of equal length, define the \emph{overlap gap between $u$ and $v$}, denoted $og(u,v)$, as the least integer $m$ for which there exist words $x$ and $x^{\prime }$ of length $m$ such that $xu=v{x}^{\prime }$ or $ux=x^{\prime }v$. Informally, the overlap gap measures the outside parts of the greatest overlap of the given words. For a left-infinite word $\lambda$ and a right-infinite word $\rho$, let $o{g}_{\lambda ,\rho }$ be the function defined, for each non-negative integer $n$, by $o{g}_{\lambda ,\rho }(n)=og({\lambda }_n,{\rho }_n)$, where ${\lambda }_n$ and ${\rho }_n$ are, respectively, the suffix of $\lambda$ and the prefix of $\rho$ of length $n$. Also, denote by $O{G}_{\lambda ,\rho }$ the image of the function $o{g}_{\lambda ,\rho }$. In this paper, we show that $O{G}_{\lambda ,\rho }$ is a finite set if and only if $\lambda$ and $\rho$ are ultimately periodic infinite words of the form $\lambda =u^{-\infty }{w}_1=\cdots uuu{w}_1$ and $\rho =w_2{u}^{\infty }=w_{2}uuu\cdots$ for some finite words $u$, $w_1$ and $w_2$.