Avoiding Generalized Repetitive Patterns in Words

我建议的研究项目是关于单词的组合数学。 这是纯数学的一个领域。 我建议的研究课题是关于单词重复的可避免性。这一领域的研究起源于阿克塞尔图厄（1906年）的工作，他展示了如何使用三个符号构建一个无限的词，使得这个词永远不会包含连续重复两次的相同符号序列。出现这种重复的图案（如“牙垢”一词）被称为“正方形”，并象征性地表示为图案XX。通过考虑各种其他类型的重复模式，Thue的工作已经在许多方面得到了推广：反转模式，循环词，阿贝尔重复，分数重复等。反转模式由重复结构组成，如XXR，它表示一个词后跟它的反转（即，偶数长度回文，如“redder”）。对这些类型的模式的兴趣是由我和柯里写的两篇论文引发的：一篇关于模式（反转）XXRX，另一篇关于模式（反转）XXXR。在每一种情况下，我们都估计了在一个二进制字母表中避免出现所讨论的模式的单词数量。我们发现，在这两种情况下，避免这种模式的单词数量都有非常不寻常的增长。在之前与Currie和Mol的合作中，我们用反转部分描述了可避免的模式。我想继续这项工作，完成特征描述。我将研究的另一个问题是关于“循环词”。圆字是指符号排列在圆上（而不是直线上）的字。最近，我们与Currie和Mol一起完成了Gorbunova（2012）关于在给定字母表上循环词可以避免重复的猜想的最后一个案例。Gorbunova的猜想涉及到对可避免性的“强”定义。 还有一些较弱的定义，类似的问题仍然悬而未决。我想研究一下这些关于可避免性的说法。图厄问题的另一个变体涉及避免阿贝尔重复。例如，正方形模式XX的阿贝尔变体由一个词组成，该词的前半部分不一定与后半部分相同，而是后半部分的变位词。例如“reappear”是XX的阿贝尔实例，因为“pear”是“reap”的变位词。与Shallit和柯里，我们计划提高目前的估计数的话长度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.