Algorithmische Kombinatorik auf Folgen

• Antragsteller: Professor Dr. Florin Manea
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2012 bis 2019
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 218587403

Das Studium kombinatorischer Eigenschaften von Wörtern war von Beginn an in der Theoretischen Informatik von Bedeutung und fand viele Anwendungen in der Sprachtheorie, Datenkomprimierung und Kryptographie. In letzter Zeit wurden neue Konzepte auf dem Gebiet der Kombinatorik auf Wörtern vorgeschlagen und entwickelt, was aus dem gestiegenen Interesse, biologische Daten, die oft als Wörter über einem eingeschränkten Alphabet dargestellt werden, zu analysieren und zu verarbeiten, entstanden ist. Wir schlagen vor, mehrere solcher Konzepte aus algorithmischer und kombinatorischer Sicht zu untersuchen. Zunächst werden wir kombinatorische Eigenschaften von partiellen Wörtern, kanonischen Erweiterungen klassischer Wörter, studieren. Dies sind Buchstaben-Folgen, bei denen neben regulären Symbolen möglicherweise auch unbekannte Symbole (Platzhalter) vorkommen, die jeweils für ein beliebiges Zeichen aus dem zugrundeliegenden Alphabet stehen. Des Weiteren werden wir Probleme untersuchen, die mit pseudo-kombinatorischen Eigenschaften von Wörtern entstehen. Dieses Konzept, das durch die Molekular-Biologie motiviert ist, kann man wie folgt zusammenfassen: Ein Wort im klassischen Sinne hat eine gewisse Eigenschaft, wenn einige seiner Teilwörter gewisse Bedingungen erfüllen; in unserem Falle verlangen wir, dass die Teilwörter oder ihre Bilder bei einer Abbildung ähnliche Bedingungen erfüllen. Schließlich werden wir auch andere Probleme angehen, die mit Operationen auf Wörtern oder numerischen Eigenschaften von Wörtern zusammenhängen.

• DFG-Verfahren: Sachbeihilfen