Kombinatorische Aspekte von Wörtern und deren Anwendungen

• Antragsteller: Professor Dr. Dirk Nowotka
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2010 bis 2018
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 181615770

Grundlegende kombinatorische Probleme über sequenzielle Objekte und deren Verarbeitung tauchen in vielen Bereichen auf. Als Beispiele seien die Analyse von großen DNS Datensätzen in der Bioinformatik, die schnelle Berechnung der konvexen Hülle aus der Kontur in der diskreten Geometrie oder die effiziente Suche in Texten genannt. Obwohl in der Vergangenheit kombinatorische Resultate über Wörter (oder Sequenzen oder Strings) sehr zum besseren Verständnis und verschiedenen algorithmischen Anwendung führten, sind erstaunlich viele grundlegende Fragen immer noch unbeantwortet. Im Rahmen dieses Projekts soll das Gebiet der Kombinatorik auf Wörtern wesentlich vorangetrieben werden. Seit langem offene Fragen über die (Un-)Vermeidbarkeit von Mustern, Wortgleichungen und -morphismen werden unter dem Gesichtspunkt neuester Methoden untersucht. Der Aspekt der Anwendbarkeit der Ergebnisse und dem Transfer von entwickelten kombinatorischen Methoden in andere Bereiche wird hier besonders Rechnung getragen. Verallgemeinerungen der entwickelten Theorie auf, zum Beispiel, ähnlicher Muster unter anti-/morphen Bildern dienen zusätzlich der Anwendbarkeit.

• DFG-Verfahren: Sachbeihilfen