Computational and Combinatorial Aspects of Strings

字符串的计算和组合方面

• 批准号: RGPIN-2018-05504
• 负责人: Franek, Frantisek
• 金额: $ 3.35万
• 依托单位: McMaster University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2022
• 资助国家: 加拿大
• 起止时间: 2022-01-01 至 2023-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=750430
• 关键词: 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)为加拿大的IT研究和行业制定HQP。本申请的研究建议涉及(A)，HQP培训计划涉及(B)和(C)。以往研究出版物的质量和数量保证了拟议研究的质量和范围的可行性；我过去的HQP努力的质量和数量(在过去的5年中，3名硕士和5名博士生成功地完成了基于先前资助计划的研究，从现在的学生中，3名硕士和2名博士生正在从事与该计划相关的研究)，以及我的研究生参与的研究出版物的数量和质量保证了(B)和(C)的可行性。研究建议集中在三个目标上：(1)分析和量化Lyndon数组和字符串的后缀数组之间的关系，目标是设计一种计算Lyndon数组的线性算法，避免了所有类型的后缀，并且与字母表的大小无关；(2)解决了双平方在最大相异平方数问题中的作用，从而解决了Fraenkel-Simpson关于相异平方的个数与弦的长度有界的猜想。这部分研究将探索一个新的概念，即逆子因子和双平方到足够小的几乎不相交的指标族的映射，作为解决猜想的可能方法；(3)由于快速的组合爆炸，游程极大或不同平方极大串的计算非常困难，它们的结构是缩小搜索空间的唯一工具。需要对它们的结构进行新的洞察，以进一步限制搜索空间。该建议讨论了缩小搜索空间的途径。建议研究的影响在于促进该领域的发展，这是信息技术的一个重要领域，并通过最先进的算法方法和软件设计培训HQP。在不久的将来，高度训练有素的信息技术人员短缺已被确定为加拿大面临的主要挑战之一。