Avoiding Generalized Repetitive Patterns in Words

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

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.