Computational and combinatorial approaches to periodicities in strings

点击翻译按钮获取中文摘要

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.