Words avoiding Repetitions: Characterizations and Algorithms

我提出的研究计划是在词的组合学和自动机理论两个领域。词的组合学是研究有限符号集合上序列的组合性质。它是离散数学和形式语言理论的交叉领域。

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.