Combinatorics of Word Morphisms

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

Combinatorial pattern matching is the area of theoretical computer science that is concerned with the study of combinatorial and algorithmic properties of finite and infinite sequences of symbols (also called words or strings). This field lies at the crossroads of algebra, combinatorics, complexity theory, and algorithms theory, and has multiple applications in data compression, cryptography, language theory, but also bioinformatics or data mining. One of the core topics within this area is the understanding of combinatorial and algorithmic properties of word-morphisms. We propose the study of word-morphisms from two points of view: algorithmic and mathematical. From an algorithmic point of view, we focus on the satisfiability problem for word equations. Given two words containing constants and variables, we are interested in whether there exists a way to replace the variables (i.e., a morphism mapping the variables to strings of constants) that makes the two words equal. This problem generalises a multitude of well studied pattern matching problems, some of them very practical and with efficient solutions, e.g., checking whether a shorter text appears in a longer one. However, the exact time complexity of deciding the satisfiability problem for word equations is not yet known. It is known that word equations can be solved in linear non-deterministic space, and that the problem is $\npclass$-hard. This suggests that, in general, constructing word-morphisms that fulfil a set of predefined conditions is a computationally hard problem. Our research on this topic proposes a thorough investigation of the complexity of the satisfiability problem for general word equations, but also for various classes of restricted, yet meaningful, equations, defined by various numerical and structural parameters, where even efficient algorithms could be obtained. From a mathematical point of view, we intend to enrich the study of combinatorial and algebraic properties of word-morphisms. Within this focus point, we are interested in the investigation of structural and combinatorial properties of equality sets (sets of words which are equal under two given morphisms). This topic has deep connections to the areas of computability and complexity. For instance, the the famous Post Correspondence Problem can be expressed as the emptiness problem for the equality set of two given morphisms. Moreover, algebraic dimension properties of systems of word equations are of interest to us. For instance, it is a long standing open problem to find the maximum size of independent systems of equations over a fixed number of variables; it is expected that solving such problems requires a good understanding of the combinatorics of morphisms that represent the solutions to independent equations.

• DFG Programme: Research Grants