


























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'$ 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^{-\infty}w_1=\cdots uuuw_1$ and $ρ=w_2u^\infty=w_2uuu\cdots$ for some finite words $u$, $w_1$ and $w_2$.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。