Computational and Combinatorial Aspects of Strings

字符串通常表现出很少的结构，但由于其广泛的适用性而引起了极大的兴趣。因此，研究人员一直对字符串中的各种周期性感兴趣，这些周期性允许对方法和算法进行有限的结构分析。如果复杂性不是问题，模式匹配中的大多数问题都是相当直接的。相关的蛮力解通常适用于二次或三次最坏时间复杂度。然而，对于DNA或蛋白质分析等许多应用所需的大字符串，这种复杂性变得难以处理。这项资助申请有多个目的：(a)继续高水平的研究工作，(b)让研究生参与高水平的研究工作，以及(c)为加拿大信息技术研究和工业生产HQP。本申请的研究计划涉及(a)， HQP培训计划涉及(b)和(c)。过去研究出版物的质量和数量保证了拟议研究的质量和范围的可行性；我过去的HQP工作的质量和数量（在过去的5年里，3名硕士和5名博士研究生成功毕业，并根据先前的资助提案进行研究，从目前的学生中，3名硕士和2名博士研究生正在进行与该提案相关的研究）以及我的研究生参与的研究出版物的数量和质量保证了(b)和(c)的可行性。本课题主要研究三个目标：(1)分析和量化字符串的林登数组与后缀数组之间的关系，设计一种线性计算林登数组的算法，避免后缀的全排序，不受字母表大小的影响；(2)解决了双平方在最大不同平方数问题中的作用，从而解决了著名的freenkel - simpson关于不同平方数受弦长度限制的猜想。这一部分的研究将探讨一种新的反演子因子的概念和双平方映射到一个足够小的几乎不相交的指标族作为解决猜想的可能方法；(3)由于快速的组合爆炸，最大运行值或最大不同平方字符串很难计算，它们的结构是缩小搜索空间的唯一工具。为了进一步限制搜索空间，需要对它们的结构有新的认识。该提案讨论了缩小搜索空间的途径。建议研究的影响是在该领域的进步，这是信息技术和HQP培训的一个重要领域，具有最先进的算法方法和软件设计。在不久的将来，训练有素的信息技术人员短缺已被确定为加拿大面临的主要挑战之一。

Strings generally exhibit very little structure, but are of a significant interest due to their wide range of applicability. Researchers have thus always been interested in various periodicities in strings that allow limited structural analysis of methods and algorithms. Most of the problems in pattern matching are rather straightforward if the complexity is not an issue. The associated brute force solutions often work with quadratic or cubic worst-time complexities. However, such complexities become intractable for large strings required by many applications such as DNA or protein analysis. This grant application has multiple aims: (a) to continue high level intensive research work, (b) to engage the graduate students in a high level research work, and (c) to produce HQP for Canadian IT research and industry.The research proposal of this application addresses (a), the HQP Training Plan addresses (b) and (c). The quality and quantity of past research publications guarantee the viability of the quality and scope of the proposed research; the quality and quantity of my past HQP efforts (in the last 5 years, 3 Master's and 5 Doctoral students successfully graduated with research based on the previous grant proposal, and from the current students, 3 Master's and 2 Doctoral students are working on the research related to this proposal) and the number and quality of research publications my graduate students participated in guarantee the viability of (b) and (c).The research proposal focuses on three objectives: (1) analyzing and quantifying the relationship between the Lyndon array and the suffix array of a string, with a goal of designing a linear algorithm computing the Lyndon array avoiding a full sort of the suffixes and independent of the size of the alphabet; (2) resolving the role of double-squares in the maximum-number-of-distinct-squares problem and so resolving the outstanding Fraenkel-Simpson's conjecture that the number of distinct squares is bounded by the length of the string. This part of the research will investigate a novel concept of inversion subfactors and the mapping of double squares to a sufficiently small almost disjoint family of indices as possible methods to resolve the conjecture; (3) as run-maximal or distinct-square-maximal strings are very hard to compute due to fast combinatorial explosion, their structure is the only tool for narrowing the search space. New insight into their structure is needed to limit the search space even more. The proposal discusses the routes to such narrowing of the search space.The impact of the proposed research is in the advancement of the field which is an important area of IT and the training of HQP with the state-of-the-art algorithmic methods and software design. The shortage of highly trained IT personnel in near future had been identified as one of major challenges for Canada.