论文标题
走在单词上
Walking on Words
论文作者
论文摘要
在某个字母上掌握任何单词。如果是非空的，请转到任何位置并打印出扫描的信件。现在，重复以下任何次数（可能为零）：停留在当前字母上，或者向左移动一个字母（如果可能的话）或向右移动一个字母（如果可能的话）；然后打印出扫描的信。实际上，我们将在输入词上散步。让u为包括访问的位置的输入单词的融合，然后打印出单词（如果输入单词为空）。由于输入单词的任何未访问的前缀或后缀都不会影响w，因此我们也可以丢弃它们，并说您生成w。我们问：给出一个单词W，您会产生什么单词？答案令人惊讶。如果您生成W，则称您为W的原始发电机，并且不会比您短的单词生成。我们表明，除了一些退化的情况外，每个单词都具有两个原始发电机。
Take any word over some alphabet. If it is non-empty, go to any position and print out the letter being scanned. Now repeat the following any number of times (possibly zero): either stay at the current letter, or move one letter leftwards (if possible) or move one letter rightwards (if possible); then print out the letter being scanned. In effect, we are going for a walk on the input word. Let u be the infix of the input word comprising the visited positions, and w the word printed out (empty if the input word is). Since any unvisited prefix or suffix of the input word cannot influence w, we may as well discard them, and say that u generates w. We ask: given a word w, what words u generate it? The answer is surprising. Call u a primitive generator of w if u generates w and is not generated by any word shorter than u. We show that, excepting some degenerate cases, every word has precisely two primitive generators.
