Computational and Combinatorial Aspects of Strings

字符串通常表现出很少的结构，但由于其广泛的适用性而引起了极大的兴趣。因此，研究人员一直对字符串中的各种周期性感兴趣，这些周期性允许对方法和算法进行有限的结构分析。如果复杂性不是问题，模式匹配中的大多数问题都是相当直接的。相关的蛮力解通常适用于二次或三次最坏时间复杂度。然而，对于DNA或蛋白质分析等许多应用所需的大字符串，这种复杂性变得难以处理。这项资助申请有多个目的：(a)继续高水平的研究工作，(b)让研究生参与高水平的研究工作，以及(c)为加拿大信息技术研究和工业生产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.