Algorithmic Combinatorics on Sequences

• Applicant: Professor Dr. Florin Manea
• Subject Area: Theoretical Computer Science
• Term: from 2012 to 2019
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 218587403

The study of the combinatorial and algorithmic properties of words is a central topic in theoretical computer science, finding many applications in data compression, cryptography, language theory, as well as in algorithmic learning theory, data-base theory, bioinformatics or molecular biology. Initially motivated by two of the central problems in combinatorics and algorithmics on words, namely pattern matching and solving word equations, we propose the investigation of a series of novel combinatorial and algorithmic questions. Among the main topics we approach, we mention: efficiently matching various types of second-order patterns (i.e., patterns that contain, besides constant symbols, both word- and function- variables), identifying relevant classes of word equations whose satisfiability can be efficiently decided, understanding where the hardness of solving other classes of word equations originates, as well as analysing approximate pattern matching problems and questions related to the possibility of factoring a word in factors with specific combinatorial properties (e.g., squares, palindromes).

• DFG Programme: Research Grants