论文标题
线性因子复杂性单词的拓扑不变性
Topological invariants for words of linear factor complexity
论文作者
论文摘要
给定有限的字母$σ$和一个右派单词$ w $上的字母$σ$，我们构造了一个拓扑空间$ {\ rm rec}（w）$，由所有右派复发单词组成，由$ w $的所有因素都是$ w $的所有因素，我们在同等的情况下都相同，如果这些因素是相同的，如果这些词相同。我们表明，$ {\ rm rec}（w）$可以赋予自然拓扑，我们表明，如果$ w $是线性因子复杂性的单词，则$ {\ rm rec}（w）$是有限的拓扑空间。此外，我们注意到有一些示例表明，如果$ f：\ mathbb {n} \ to \ mathbb {n} $倾向于无穷大，则是$ n \ to \ infty $的函数，然后有一个单词的因子复杂性函数$ {\ rm o}（nf（nf（n））$ rec $ rec $ rec}（\ rm rem} \ rm rm rm rm rm rm rm rm rm rm rm rm rm rm rm rm rm rm rm rm rm rm rm {最后，我们提出了一个实现问题：对于线性因子复杂性，可以出现哪些有限拓扑空间为$ {\ rm rec}（w）$？
Given a finite alphabet $Σ$ and a right-infinite word $w$ over the alphabet $Σ$, we construct a topological space ${\rm Rec}(w)$ consisting of all right-infinite recurrent words whose factors are all factors of $w$, where we work up to an equivalence in which two words are equivalent if they have the exact same set of factors (finite contiguous subwords). We show that ${\rm Rec}(w)$ can be endowed with a natural topology and we show that if $w$ is word of linear factor complexity then ${\rm Rec}(w)$ is a finite topological space. In addition, we note that there are examples which show that if $f:\mathbb{N}\to \mathbb{N}$ is a function that tends to infinity as $n\to \infty$ then there is a word whose factor complexity function is ${\rm O}(nf(n))$ such that ${\rm Rec}(w)$ is an infinite set. Finally, we pose a realization problem: which finite topological spaces can arise as ${\rm Rec}(w)$ for a word of linear factor complexity?
