Avoiding Generalized Repetitive Patterns in Words

避免单词中的普遍重复模式

• 批准号: RGPIN-2019-04111
• 负责人: Rampersad, Narad
• 金额: $ 1.24万
• 依托单位: University of Winnipeg
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2019
• 资助国家: 加拿大
• 起止时间: 2019-01-01 至 2020-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=675818
• 关键词: Avoiding; Generalized; Repetitive; Patterns; Words

My proposed research program is in the area of combinatorics on words. This is an area of pure mathematics. My proposed research is on the topic of the avoidability of repetitions in words. This area of study originated with the work of Axel Thue (1906), who showed how to construct an infinite word using just three symbols such that this word never contains the same sequence of symbols repeated twice in a row. An occurrence of such a repetitive pattern (like the word "tartar") is called a "square" and is represented symbolically as the pattern XX. Thue's work has been generalized in many ways by considering various other types of repetitive patterns: patterns with reversal, circular words, abelian repetitions, fractional repetitions etc.******Patterns with reversal consist of repetitive structures such as XXR, which denotes a word followed by its reversal (i.e., an even length palindrome like "redder"). Interest in these types of patterns was sparked by two papers I wrote with Currie: one on the pattern (with reversal) XXRX and the other on the pattern (with reversal) XXXR. In each case we estimated the number of words over a binary alphabet that avoided the pattern in question. We found that in both cases the number of words avoiding the pattern had a very unusual growth. In previous work with Currie and Mol, we partially characterized the avoidable patterns with reversal. I would like to continue this work and complete the characterization.******Another problem that I will study concerns "circular words". A circular word is a word whose symbols are arranged on a circle (rather than linearly on a straight line). Recently, with Currie and Mol, we completed the last cases of a conjecture of Gorbunova (2012) concerning which repetitions could be avoided by circular words over a given alphabet. Gorbunova's conjecture involved a "strong" definition of avoidability. There are weaker definitions for which the analogous questions remain open. I would like to study these versions of avoidability.******Another variant of Thue's problem concerns the avoidance of Abelian repetitions. For example, the Abelian variant of the square pattern XX instead consists of a word whose first half is not necessarily identical to its second half, but rather is an anagram of its second half. For example "reappear" is an Abelian instance of XX, since "pear" is an anagram of "reap". With Shallit and Currie, we plan to improve the current estimates on the number of words of length n that avoid abelian squares, cubes, etc. ******This research is theoretical in nature; the most common applications of combinatorics on words are to other areas of mathematics, such as algebra and number theory. However, some results in this area have been successfully applied to problems in bioinformatics (like sequence assembly,where short DNA strings are assembled into whole genome sequences), random number generation, and coding theory.**

我建议的研究项目是关于单词的组合学领域。这是一个纯粹的数学领域。我提出的研究是关于词中重复的可避免性这一主题。这一领域的研究起源于Axel Thue(1906年)的工作，他展示了如何仅使用三个符号来构建一个无限的单词，从而使这个单词永远不会包含连续重复两次的相同符号序列。这种重复的图案(如单词“tartar”)的出现被称为“正方形”，并象征性地表示为图案XX。通过考虑各种其他类型的重复模式，图厄的工作已经在许多方面得到了推广：具有反转的模式、圆形单词、阿贝尔重复、分数重复等。*具有反转的模式由重复结构组成，例如XXR，它表示一个单词后面跟着它的反转(即，像“redder”这样的偶数长度回文)。我和Currie一起写的两篇论文激发了人们对这类模式的兴趣：一篇是关于模式(有反转)XXRX的，另一篇是关于模式(有反转)XXXR的。在每种情况下，我们都估计了避免出现上述模式的二进制字母表上的单词数量。我们发现，在这两种情况下，避免该模式的单词数量都有非常不寻常的增长。在之前与Currie和Mol的工作中，我们用反转部分刻画了可避免的模式。我想继续这项工作，完成刻画。*我将研究的另一个问题是“循环词”。圆形单词是其符号排列在圆圈上(而不是直线上)的单词。最近，我们与Currie和Mol一起完成了Gorbunova(2012)的一个猜想的最后几个例子，关于这个猜想，重复可以通过给定字母表上的循环词来避免。戈尔布诺娃的猜想包含了对可避免性的“强有力的”定义。还有一些较弱的定义，类似的问题仍然悬而未决。我想研究这些版本的可避性。*图的问题的另一个变种是关于避免阿贝尔重复。例如，正方形图案XX的阿贝尔变体由一个单词组成，该单词的前半部分不一定与其后半部分相同，而是其后半部分的字谜。例如，“re现”是XX的Abelian实例，因为“pear”是“reap”的变形词。有了Shallit和Currie，我们计划改进目前对长度为n的避免阿贝尔正方形、立方体等的单词数量的估计。*这项研究本质上是理论的；组合学对单词的最常见应用是在其他数学领域，如代数和数论。然而，这一领域的一些结果已经成功地应用于生物信息学(如序列组装，其中短DNA串组装成整个基因组序列)、随机数生成和编码理论等问题。