论文标题
无限单词的开放和封闭的复杂性
Open and closed complexity of infinite words
论文作者
论文摘要
在本文中，我们研究了在无限单词上定义的两个相对复杂性函数的渐近行为及其与周期性的关系。给定一个因子$ u $的无限单词$ x $，我们说$ u $如果是字母，或者是$ x $的某个因素$ v $的完全首次返回；否则$ u $据说是开放的。我们表明，对于有限字母上的Aperiodic Word $ x $，计算闭合数量的复杂性功能和每个给定长度的$ x $的开放因素的数量都是无限的。更确切地说，我们表明，如果$ x $是一个aperiodic，那么开放式复杂性功能的极限是无限的，并且在正整数的任何联合子集中，闭合复杂性功能的极限是无限的。另一方面，存在闭合复杂性函数较低的限制的多个词是有限的。
In this paper we study the asymptotic behaviour of two relatively new complexity functions defined on infinite words and their relationship to periodicity. Given a factor $u$ of an infinite word $x$, we say $u$ is closed if it is a letter or if it is a complete first return to some factor $v$ of $x$; otherwise $u$ is said to be open. We show that for an aperiodic word $x$ over a finite alphabet, the complexity functions that count the number of closed and the number of open factors of $x$ of each given length are both unbounded. More precisely, we show that if $x$ is aperiodic then the limit inferior of the function of open complexity is infinite, and the limit superior of the function of closed complexity is infinite on any syndetic subset of positive integers. On the other hand, there exist aperiodic words for which limit inferior of the closed complexity function is finite.
