Dependable Systems Group

DFG Algorithmic Combinatorics on Words (2013-18)

May 01, 2013

The Deutsche Forschungsgemeinschaft (DFG) funds Florin Manea's research on algorithmic combinatorics on words. The study of the combinatorial properties of words finds many applications in language theory, data compression or cryptography. Nowadays, a series of new concepts, belonging to this topic, were developed following an increased interest in the study and processing of biological data, which are represented as words over a restricted alphabet. As such data usually comes in huge amounts, we propose the study of several combinatoric concepts from an algorithmic point of view. The problems we investigate require processing different types of words using efficient algorithms, which exploit their combinatorial structure. On one hand, we solve problems regarding partial words, canonical extensions of the classical words that can be used to model data with errors. Besides regular symbols, such words contain unknown symbols that can stand for any of the regular symbols of the working alphabet. On the other hand, we investigate classes of words that can be described by common properties of their factors as well as of the images of their factors under certain functions. Such words have less obvious (even hidden) combinatorial structure, that may be important in applications. Several other problems, related to operations on words and numerical properties of words are approached.

Duration: May 2013 until April 2016 (extension from 01.11.2016 until 31.10.2018)

Funds: 227,000 EUR (+ 147,000 EUR)