Words avoiding Repetitions: Characterizations and Algorithms

我提出的研究计划是在词的组合学和自动机理论这两个领域。词的组合学是研究有限符号集上序列的组合性质的学科。这是一个离散数学和形式语言理论的交叉领域。*我特别感兴趣的是避免单词中的重复。我以前在该地区的工作有助于解决德简猜想，这是该地区一个长期悬而未决的问题。关于单词重复的许多其他有趣的悬而未决的问题仍有待解决。利用为证明德简猜想而发展起来的技术，我建议研究达到猜想(现在的定理)所描述的重复阈值的单词的结构。这种单词的特征在二进制字母表上是已知的，但对于更大的字母表目前还不存在这样的理论。对于更大的字母表，这种类型的表征可能会在先验数论中产生新的结果(就像二进制字母表的情况一样)。*我还建议研究计数系统理论中出现的无限单词。从最广泛的意义上讲，计数系统就是用单词表示整数的系统。经典的以整数为基数的计数系统是这种计数系统的特例。可以由以k为基数处理其输入的有限自动机计算的整数序列称为k-自动机序列。K-自动序列的许多组合属性，例如周期性或避免重复，在算法上是可判定的。然而，目前还没有通用的程序来确定k-自动序列是否避免了阿贝尔重复(形式xx‘的重复，其中x’是x的排列)。最近，我们与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.****