Servicenavigation

Project Details

Back

Projekt Print View

Combinatorics of Word Morphisms

Subject Area Theoretical Computer Science
Term from 2018 to 2023
Project identifier Deutsche Forschungsgemeinschaft (DFG) - Project number 389613931
 
Final Report Year 2024

Final Report Abstract

This project was focused on two main directions. On the one hand, we wanted to develop combinatorial and language theoretic tools allowing us to get a better understanding of the complexity of solving word equations, potentially of restricted form, and to obtain more insights in the structure of the solution-sets for such equations. On the other hand, we wanted to also perform a more general study of the combinatorial and algorithmic properties of word-morphisms, extending beyond the scope of word equations. The main result that we have obtained regarding word equations is the following. Starting from the fact that for quadratic word equations there exists an algorithm based on rewriting rules which generates a directed graph describing all solutions to the equation, we were able to show that, in the case of regular word equations – those for which each variable occurs at most once on each side of the equation –, this graph has nice combinatorial properties. In particular, we were able to show polynomial bounds on its diameter, size, and DAG-width, as well as to obtain some deeper insights into symmetries in its structure. As a consequence, we have obtained a combinatorial proof that the problem of deciding whether a regular word equation has a solution is in NP. This breakthrough result concluded a longer line of research on regular and quadratic word equations, and exhibits one of the largest classes of word equations whose satisfiability is in NP. These results were complemented by a series of investigations, of both theoretical and practical nature, regarding the decidability of other classes of string constraints (that is, word equations with additional linear length constraints and language membership constraints). In the area of the study of combinatorial and algorithmic properties of word-morphisms, our main results come from the investigation of morphisms mapping words to their set of subsequences of a given length. In particular, we have solved a long standing open problem, stated by Imre Simon in the 1970s, by showing that one can compute in linear time the largest number k such that two input words have exactly the same set of subsequences of length k. This result came as the combination of some deep combinatorial observations with the construction of novel efficient data structures. Moreover, it opened a fruitful line of research regarding combinatorial pattern matching and analysis problems for the subsequence-sets of strings.

Publications

 
 

Additional Information

© 2025 DFG Disclaimer / Copyright / Privacy Policy

Textvergrößerung und Kontrastanpassung