Words avoiding Repetitions: Characterizations and Algorithms

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

• 批准号: 418646-2012
• 负责人: Rampersad, Narad
• 金额: $ 1.24万
• 依托单位: University of Winnipeg
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2018
• 资助国家: 加拿大
• 起止时间: 2018-01-01 至 2019-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=662971
• 关键词: 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-自动序列是否避免阿贝尔重复（形式为xx'的重复，其中x'是x的置换）。我们最近与James Currie一起提出了一种适用于一大类序列的算法。我想开发一个完全通用的算法程序。