Computational and combinatorial approaches to periodicities in strings

字符串的周期性在许多应用中都很重要，例如数据压缩、文本检索、DNA或蛋白质测序等。弦的基本周期包括不同的平方和游程。我的建议有两个目标，主要是更深入地了解基本周期及其计算，其次是提高图形的上限，从而反驳埃尔德什猜想。 其主要目标是实现更深入的了解字符串的结构特征，表现出最大数量的运行或最大数量的不同的平方米采用一种新的d-步骤的分析方法，可以应用到这两个尽管问题的多样性。这包括为不同的平方和游程提供更好的n-d的具体（非渐近）上界，其中n是字符串的长度，d是其字母表的大小，并设计更有效的算法，通过利用游程或平方最大字符串的结构特性来计算不同的平方或游程。 该建议的第二部分涉及建立一个有效的计算框架，用于搜索图，以实现对埃尔德什关于团的多重性的猜想的改进的上界。该搜索由基于二进制字符串的种子引导。到目前为止，该方法确认了已知的结果，并改进了大小为6，7和8的集团的界限。所提出的研究的目的是在这两个，改善现有的小规模的集团，以及为更大的规模到目前为止，计算上难以处理的界限。 监督和培训高素质的人才是我的研究建议的重要组成部分。作为高级优化实验室（AdvOL）的副主任，我将继续寻找优秀的研究生，并进一步加强AdvOL的工作。这将有助于开发模型，算法，软件，并为加拿大的信息技术培养高素质的人才。

The periodicities of strings are of interest for many applications such as data compression, text retrieval, and DNA or protein sequencing. The fundamental periodicities in a string include distinct squares and runs. My proposal has two objectives, the main dealing with a deeper understanding of the fundamental periodicities and their computations, and the secondary with improving upper bounds to graphs disproving an Erdös' conjecture. The main objective is to achieve a deeper understanding of the structural characteristics of strings exhibiting maximal number of runs or maximal number of distinct squares employing a novel d-step analytic approach that can be applied to both despite the diversity of the problems. This includes providing better concrete (non-asymptotic) upper bounds of n-d for both distinct squares and runs, where n is the length of the string and d is the size of its alphabet, and design of more efficient algorithms for computing distinct squares or runs by exploiting the structural properties of run- or square-maximal strings. A secondary part of the proposal deals with establishing an efficient computational framework for search of graphs achieving improved upper bounds to Erdös' conjecture on multiplicities of cliques. The search is directed by binary-string based seeds. The approach so far yielded confirmation of known results and improved bounds for cliques of size 6, 7, and 8. The proposed research aims at both, improving the existing bounds for small size cliques as well as for larger sizes so far computationally intractable. Supervision and training of highly qualified personnel is an essential part of my research proposal. As the deputy head of the Advanced Optimization Laboratory (AdvOL), I will continue to seek top graduate students, and further strengthen the working of AdvOL. This will help develop models, algorithms, software, and produce highly qualified personnel for Information Technology in Canada.