Computational and Combinatorial Aspects of Strings

字符串的计算和组合方面

• 批准号: RGPIN-2018-05504
• 负责人: Franek, Frantisek
• 金额: $ 1.68万
• 依托单位: McMaster University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2020
• 资助国家: 加拿大
• 起止时间: 2020-01-01 至 2021-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=713009
• 关键词: Computational; Combinatorial; Aspects; Strings

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.

弦通常表现出非常小的结构，但由于其广泛的适用性而受到极大的关注。因此，研究人员一直对字符串中的各种周期性感兴趣，这些周期性允许有限的方法和算法的结构分析。如果复杂性不是问题，那么模式匹配中的大多数问题都是相当简单的。相关的暴力解决方案通常具有二次或三次最坏时间复杂度。然而，这样的复杂性变得棘手的许多应用程序，如DNA或蛋白质分析所需的大型字符串。这项资助申请有多个目的：（a）继续高水平的密集研究工作，（B）从事研究生在高水平的研究工作，（c）产生HQP加拿大IT研究和行业。 本申请的研究建议涉及（a），HQP培训计划涉及（B）和（c）。过去研究出版物的质量和数量保证了拟议研究的质量和范围的可行性;我过去HQP工作的质量和数量（在过去的5年中，3名硕士和5名博士生成功毕业，研究基于以前的赠款建议，并从目前的学生，3名硕士生和2名博士生正在进行与本提案相关的研究），我的研究生参与的研究出版物的数量和质量保证了（B）和（c）的可行性。 本文的研究目标主要有三个：（1）分析和量化字符串的Lyndon数组与后缀数组之间的关系，设计一种线性算法来计算Lyndon数组，避免了后缀的全排序，并且与字母表的大小无关;（2）解决了双平方在最大相异平方数问题中的作用，从而解决了悬而未决的Fraenkel-辛普森猜想不同的正方形的数量是由字符串的长度限制的。这部分的研究将探讨一个新的概念，反演子因子和双平方映射到一个足够小的几乎不相交的家庭的指数作为可能的方法来解决这个猜想;（3）运行最大或不同平方最大字符串是非常困难的计算，由于快速组合爆炸，他们的结构是唯一的工具，以缩小搜索空间。需要对它们的结构进行新的了解，以进一步限制搜索空间。该提案讨论了缩小搜索空间的途径。 所提出的研究的影响是在该领域的进步，这是一个重要的IT领域和HQP的培训与国家的最先进的算法方法和软件设计。在不久的将来，训练有素的信息技术人员的短缺被认为是加拿大面临的主要挑战之一。