Dependable Systems Group

DFG Combinatorial Aspects of Words and their Applications (2011-18)

May 07, 2012

The Deutsche Forschungsgemeinschaft (DFG) funds our research on combinatorial problems of sequences (aka words). Fundamental combinatorial problems about sequential objects and the processing of them appear in many areas. Examples are the analysis of large DNA data sets in the field of computational biology, the fast calculation of the convex hull from the contour word in discrete geometry, and efficient text search. Although, for quite some time results from combinatorics on words (aka sequences or strings) have contributed to a better understanding of that data structure and lead to several algorithmic applications surprisingly many basic questions are still open.

Combinatorics on words shall be substantially further advanced within this project. Longstanding open problems about the periodicity of words, word equations and mor- phisms are investigated with recently found results and methods. The aspect of the applicability of results and the transfer of the developed combinatorial methods to other fields is particularly emphasized. Generalizations of the developed theory to, for ex- ample, partial words and multidimensional patterns additionally serves the applicability aspect.

This project has been extended by two years and additionally equipped with a Mercator professorship.

Duration: May 2011 until October 2014 (extension from November 2014 until October 2018)

Funds: 365,000 EUR (+ 320,400 EUR)