Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

McMaster University

$46,000.00

Computational and Combinatorial Aspects of Strings

FY 2022-23

Summary
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.
Program
Discovery Grants Program - Individual
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
RGPIN-2018-05504
Name nom
Franek, Frantisek
Department département
Computing and Software - Computing and Software
Organization id
27
Institution établissement
McMaster University
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2022
Competition year année de concours
2018
Award amount
46000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR LA DÉCOUVERTE
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
802
Area of application group en
Information and communication services
Area of application group fr
Services d'information et de télécommunications
Area of application en
Information systems and technology
Area of application fr
Systèmes d'information et technologie de l'information
Research subject code
2700
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Information technology
Research subject fr
Technologie de l'information
Installment
inst:5;6
Partie
2
Nb partie
6
Application title
Computational and Combinatorial Aspects of Strings
Application summary
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.