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.