Words avoiding Repetitions: Characterizations and Algorithms

我提出的研究计划是在词的组合学和自动机理论两个领域。词的组合学是研究有限符号集合上序列的组合性质。它是离散数学和形式语言理论的交叉领域。****我对避免单词的重复特别感兴趣。我之前在该领域的工作有助于解决德让猜想，这是该领域一个长期存在的开放性问题。关于单词中的重复，还有许多其他有趣的开放性问题有待解决。使用为证明德让猜想而开发的技术，我建议研究达到该猜想（现在的定理）所描述的重复阈值的单词的结构。这些词的特征已经在二进制字母表中被发现，但目前还没有这样的理论存在于更大的字母表中。对于更大的字母，这种类型的表征可能会导致超越数论的新结果（就像二进制字母的情况一样）。****我还建议研究在计数系统理论中出现的无限词。从最广泛的意义上讲，记数系统就是用单词表示整数的系统。经典整数基数记数系统是这种记数系统的一种特殊情况。可以由以k为基数处理输入的有限自动机计算的整数序列称为k-自动序列。k-自动序列的许多组合特性，如周期性或避免重复，都是算法可决定的。然而，目前还没有通用的程序来确定k-自动序列是否避免了阿贝尔重复（其中x‘是x的排列形式的xx’的重复）。最近，我们和James Currie一起提出了一种算法，可以处理大量的序列。我想开发一个完全通用的算法程序。****

My proposed research program is in the two areas of combinatorics on words and automata theory. Combinatorics on words is the study of the combinatorial properties of sequences over a finite set of symbols. It is an area at the intersection of discrete mathematics and formal language theory.****I am especially interested in the avoidance of repetitions in words. My previous work in the area contributed to the resolution of Dejean's Conjecture, a long-standing open problem in the area. Many other interesting open problems concerning repetitions in words remain to be solved. Using the techniques developed for the proof of Dejean's Conjecture, I propose to investigate the structure of the words that achieve the repetition threshold described by the conjecture (now theorem). A characterization of such words is already known over the binary alphabet, but no such theory currently exists for larger alphabets. A characterization of this type for larger alphabets could lead to new results in transcendental number theory (as was the case for the binary alphabet).****I also propose to study the infinite words that arise in the theory of numeration systems. A numeration system in the broadest sense is simply a system for representing integers by words. The classical integer base numeration systems are a special case of such numeration systems. A sequence of integers that can be computed by a finite automaton that processes its input in base-k is called a k-automatic sequence. Many combinatorial properties of k-automatic sequences, such as periodicity, or avoidance of repetitions, are algorithmically decidable. However, there is currently no general procedure to decide if a k-automatic sequence avoids Abelian repetitions (repetitions of the form xx' where x' is a permutation of x). With James Currie, we recently presented an algorithm that works on a large class of sequences. I would like to develop an algorithmic procedure that is completely general.****