Computational and combinatorial approaches to periodicities in strings

字符串周期性的计算和组合方法

• 批准号: 25112-2012
• 负责人: Franek, Frantisek
• 金额: $ 1.02万
• 依托单位: McMaster University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2015
• 资助国家: 加拿大
• 起止时间: 2015-01-01 至 2016-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=568704
• 关键词: Computational; combinatorial; approaches; periodicities; strings

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.

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