Words avoiding Repetitions: Characterizations and Algorithms

避免重复的单词：特征和算法

• 批准号: 418646-2012
• 负责人: Rampersad, Narad
• 金额: $ 1.24万
• 依托单位: University of Winnipeg
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2017
• 资助国家: 加拿大
• 起止时间: 2017-01-01 至 2018-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=635571
• 关键词: Words; avoiding; Repetitions; Characterizations; 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.

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