Boundaries of Computability in Problems on Words

• Applicant: Professor Dr. Dirk Nowotka
• Subject Area: Theoretical Computer Science
• Term: since 2020
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 437493335

As it is natural in many situations to represent data sequentially, strings of symbols (words) are a fundamental and pervasive data structure with important properties in a vast range of areas including bioinformatics, data mining and data-compression, as well as in purely mathematical contexts such as abstract algebra. Moreover, since words are often a fundamental part of classical computational models, there are many surprisingly simple undecidable problems such as the famous Post Correspondence Problem (PCP). Often, these problems can be attributed one or more natural parameters (e.g. number of tiles in PCP) and these parameters, when sufficiently limited, lead to decidable variants of the problems. The closely related theories of pattern languages and word equations yield examples of such fundamental problems on words for which there are many natural (non-)numerical and numerical parameters and often restricting these parameters in various ways can lead to both undecidable and decidable variants. The aim of this project is to better understand the boundary between computability in these settings, and to categorise particularly well-motivated variants. Since both word equations and patterns deal with the intrinsic structural properties of words, it is unsurprising that they are important in a range of applications, i.e. pattern matching, machine learning, data mining, cyber security, database theory, unification and algebra.There are also fundamental reasons to study the precise boundaries between undecidable and decidable variants of problems. Proving undecidability is usually done by reducing the problem at hand to existing problems already known to be undecidable. Thus, a small gap in the knowledge can quickly proliferate and lead to larger jumps between decidable and undecidable variants of problems whose undecidability proof(s) may be the result of several consecutive imprecise reductions. Similarly, identifying new decidable cases necessarily requires novel techniques for approaching these problems and is thus of intrinsic interest to the respective theories and their related topics.

• DFG Programme: Research Grants