论文标题
无平方的单词还原
Square-free reducts of words
论文作者
论文摘要
一个\ emph {square}是一个有限的非空词，由两个相同的相邻块组成。单词是\ emph {nree-fore-free}，如果它不包含正方形作为因素。在任何有限词中，一个人都可以删除正方形的重复块，从而获得一个较短的单词。通过重复此过程，最终达到了一个无方的单词，我们将其称为原始单词的\ emph {还原}。 一个单词可能有多少个不同的减排？并不难证明任何二进制单词都具有一个还原。我们证明存在任意减少的三元词。此外，计算最大还原数量的功能，长度为$ n $的三元单词可能会呈指数增长。我们还证明，超过四个字母，有任何给定数量的还原数量的单词，这似乎不是三元字的情况。最后，我们证明所有有限三元单词的集合将有限的许多类别\ emph {相关}单词分开（一个人可以通过一系列平方降低和因子重复的顺序从一个单词到另一个单词）。关于通过平方减少的单词定义的单词上的一些结构提出了一些开放问题。
A \emph{square} is a finite non-empty word consisting of two identical adjacent blocks. A word is \emph{square-free} if it does not contain a square as a factor. In any finite word one may delete the repeated block of a square, obtaining thereby a shorter word. By repeating this process, a square-free word is eventually reached, which we call a \emph{reduct} of the original word. How many different reducts a single word may have? It is not hard to prove that any binary word has exactly one reduct. We prove that there exist ternary words with arbitrarily many reducts. Moreover, the function counting the maximum number of reducts a ternary word of length $n$ may have grows exponentially. We also prove that over four letters, there exist words with any given number of reducts, which does not seem to be the case for ternary words. Finally, we demonstrate that the set of all finite ternary words splits into finitely many classes of \emph{related} words (one may get from one word to the other by a sequence of square reductions and factor duplications). A few open questions are posed concerning some structures on words defined with the use of the square reduction.
