Combinatorial Aspects of Words and their Applications

• Applicant: Professor Dr. Dirk Nowotka
• Subject Area: Theoretical Computer Science
• Term: from 2010 to 2018
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 181615770

Questions about combinatorial properties of sequential objects and their processing arise in many areas. The analysis of large DNA data sets in the field of computational biology, the efficient calculation of the convex hull of a contour in the field of discrete geometry, or the efficient search in large texts shall serve as examples. Despite the fact that combinatorial results on words (aka sequences aka strings) led to a much better understanding and several algorithmic applications, surprisingly many basic questions are still open. The field of combinatorics on words shall be significantly advances with this project. Longstanding open problems on the (un-)avoidability of patterns, word equations, and word morphisms are investigated with novel methods. The aspect of the application of results and the transfer of new combinatorial methods to other areas is particularly emphasised here. Generalisations of established theories, like similarity patterns under anti-/morphic images, additionally serve the applicability in other areas.

• DFG Programme: Research Grants