错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Asymptotic behavior of the overlap gap between infinite words

  • J. C. Costa,
  • C. Nogueira,
  • M. L. Teixeira

摘要

We proceed with the study of ultimate periodicity properties related to overlaps between the suffixes of a left-infinite word \(\lambda \) λ and the prefixes of a right-infinite word \(\rho \) ρ . For a positive integer n, let g(n) be n minus the maximum length of overlaps between the suffix of \(\lambda \) λ and the prefix of \(\rho \) ρ of length n. In a recent publication we have shown that the function g has finite image if and only if \(\lambda \) λ and \(\rho \) ρ are ultimately periodic words with a same root. In this paper we give an asymptotic characterization of words \(\lambda \) λ and \(\rho \) ρ for which the function g has finite image. We prove that this condition is true if and only if the sequence \(\big (g(n)/n\big )_n\) ( g ( n ) / n ) n tends to zero