Avoiding Generalized Repetitive Patterns in Words

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

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

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