Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

McMaster University

$14,000.00

Computational and combinatorial approaches to periodicities in strings

EF 2013-14

Résumé
The periodicities of strings are of interest for many applications such as data compression, text retrieval, and DNA or protein sequencing. The fundamental periodicities in a string include distinct squares and runs. My proposal has two objectives, the main dealing with a deeper understanding of the fundamental periodicities and their computations, and the secondary with improving upper bounds to graphs disproving an ErdËs' conjecture.The main objective is to achieve a deeper understanding of the structural characteristics of strings exhibiting maximal number of runs or maximal number of distinct squares employing a novel d-step analytic approach that can be applied to both despite the diversity of the problems. This includes providing better concrete (non-asymptotic) upper bounds of n-d for both distinct squares and runs, where n is the length of the string and d is the size of its alphabet, and design of more efficient algorithms for computing distinct squares or runs by exploiting the structural properties of run- or square-maximal strings.A secondary part of the proposal deals with establishing an efficient computational framework for search of graphs achieving improved upper bounds to ErdËs' conjecture on multiplicities of cliques. The search is directed by binary-string based seeds. The approach so far yielded confirmation of known results and improved bounds for cliques of size 6, 7, and 8. The proposed research aims at both, improving the existing bounds for small size cliques as well as for larger sizes so far computationally intractable.Supervision and training of highly qualified personnel is an essential part of my research proposal. As the deputy head of the Advanced Optimization Laboratory (AdvOL), I will continue to seek top graduate students, and further strengthen the working of AdvOL. This will help develop models, algorithms, software, and produce highly qualified personnel for Information Technology in Canada.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Ontario, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
25112-2012
Name nom
Franek, Frantisek
Department département
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
2013
Competition year année de concours
2012
Award amount
14000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à 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
2713
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Algorithms
Research subject fr
Algorithmes
Partie
2
Nb partie
5
Application title
Computational and combinatorial approaches to periodicities in strings
Keyword
NSERC
Application summary
The periodicities of strings are of interest for many applications such as data compression, text retrieval, and DNA or protein sequencing. The fundamental periodicities in a string include distinct squares and runs. My proposal has two objectives, the main dealing with a deeper understanding of the fundamental periodicities and their computations, and the secondary with improving upper bounds to graphs disproving an ErdËs' conjecture.The main objective is to achieve a deeper understanding of the structural characteristics of strings exhibiting maximal number of runs or maximal number of distinct squares employing a novel d-step analytic approach that can be applied to both despite the diversity of the problems. This includes providing better concrete (non-asymptotic) upper bounds of n-d for both distinct squares and runs, where n is the length of the string and d is the size of its alphabet, and design of more efficient algorithms for computing distinct squares or runs by exploiting the structural properties of run- or square-maximal strings.A secondary part of the proposal deals with establishing an efficient computational framework for search of graphs achieving improved upper bounds to ErdËs' conjecture on multiplicities of cliques. The search is directed by binary-string based seeds. The approach so far yielded confirmation of known results and improved bounds for cliques of size 6, 7, and 8. The proposed research aims at both, improving the existing bounds for small size cliques as well as for larger sizes so far computationally intractable.Supervision and training of highly qualified personnel is an essential part of my research proposal. As the deputy head of the Advanced Optimization Laboratory (AdvOL), I will continue to seek top graduate students, and further strengthen the working of AdvOL. This will help develop models, algorithms, software, and produce highly qualified personnel for Information Technology in Canada.