String Constraint Solving: Combinatorial, Algorithmic, and Language-Theoretic Approaches

• Applicant: Professor Dr. Florin Manea
• Subject Area: Theoretical Computer Science
• Term: since 2025
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 562495345

Strings (words or sequences of symbols) are a fundamental data type, occurring in most domains of computer science, e.g., as the main way that users input data to a program, as well as the primary way for providing information back to the user. As such, understanding the fundamental mathematical properties of strings and designing efficient processing methods for them is a central task in theoretical computer science, with deep and important practical applications. In this project, we address a series of fundamental problems from the area of combinatorics and algorithmics on strings (for short, stringology), as well as their potential applications in other areas of computer science, such as formal verification. String Constraint Solving (for short, String Solving) is a topic arising in this context, which lately came to prominence in the area of formal methods, and has deep roots in the theory of word equations and, as such, in algebra and formal languages theory. This area of research abounds in hard, longstanding open problems (for instance, settling the decidability of word equations with linear length constraints, a problem deeply related to Hilbert's Tenth Problem), whose resolution would have important practical applications. Mainly, we aim to make significant progress towards solving the central open problems in the area of string solving. Moreover, we will consider several interesting related problems, which arise when investigating some particular classes of string constraints, motivated by practical scenarios. Our approach, while based on combinatorial and formal language or automata theoretic tools, has an important algorithmic component, and a desired by-product of our work consists in the development of performant practical string constraint solvers. Overall, we expect that this project will lead to significant and impactful progress in, on the one hand, theoretical computer science (in particular in areas such as formal languages and stringology), as well as, on the other hand, in the connected, practical areas.

• DFG Programme: Research Grants