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.