论文标题
扩展和减少无平方单词
Extensions and reductions of square-free words
论文作者
论文摘要
如果一个单词不包含$ xx $的非空词，则无平方。 Thue的著名结果断言，在$ 3 $的字母上有任意长的无正方形单词。我们研究无正方形单词，具有涉及单个字母缺失和单词扩展的其他属性。 如果删除任何单个字母，则无方词是稳定的。我们证明，在$ 4 $的字母上存在无限的稳定单词。我们还证明，可以通过从分配给构造单词位置的任意字母$ 7 $的任意字母中挑选出任何长度的稳定单词。我们猜测，这两个界限都可以降低到$ 4 $，这是最好的。 在相反的方向上，我们考虑在单词中每个可能的位置插入单个（适当选择的）字母后，这些单词保持无平方。我们称它们为分叉。我们证明了一个令人惊讶的事实，即在带有至少三个字母的固定字母上，每个稳定的单词都是分叉的。我们还考虑具有自然树结构的分叉单词的家庭。特别是，我们证明存在一棵无限的无限分叉单词，上面是$ 12 $的字母。
A word is square-free if it does not contain a nonempty word of the form $XX$ as a factor. A famous 1906 result of Thue asserts that there exist arbitrarily long square-free words over a $3$-letter alphabet. We study square-free words with additional properties involving single-letter deletions and extensions of words. A square-free word is steady if it remains square-free after deletion of any single letter. We prove that there exist infinitely many steady words over a $4$-letter alphabet. We also demonstrate that one may construct steady words of any length by picking letters from arbitrary alphabets of size $7$ assigned to the positions of the constructed word. We conjecture that both bounds can be lowered to $4$, which is best possible. In the opposite direction, we consider square-free words that remain square-free after insertion of a single (suitably chosen) letter at every possible position in the word. We call them bifurcate. We prove a somewhat surprising fact, that over a fixed alphabet with at least three letters, every steady word is bifurcate. We also consider families of bifurcate words possessing a natural tree structure. In particular, we prove that there exists an infinite tree of doubly infinite bifurcate words over alphabet of size $12$.
