Arbeitsgruppe Zuverlässige Systeme

DFG "Kombinat. Aspekte von Wörtern und deren Anwendungen" (2011-14)

07.05.2012

Die Sachbeihilfe der Deutschen Forschungsgemeinschaft (DFG) richtet sich an die Erforschung kombinatorischer Probleme von Sequenzen (bzw. Wörtern). 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 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 Periodizität von Wörtern, Wortgleichungen und -morphismen werden unter dem Gesichtspunkt neuer 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, partielle Wörter und mehrdimensionale Muster dienen zusätzlich der Anwendbarkeit.

Projektzeitraum: 01.05.2011 bis 31.10.2014

Projektförderung: 365.000 EUR