The project is the outcome of a recent collaboration between the Universities of Stuttgart (Volker Diekert) and Trier (Henning Fernau and Petra Wolf). It combines theory of computation, formal languages, and automata theory. More specifically, the research is about families of graphs specified by regular languages, and their properties. Traditionally, graph algorithms get a single graph as input, and then the algorithms should decide if this graph satisfies a certain property P. What happens if this question is modified in a way that we get a possibly infinite family of graphs as an input, and the question is if there exists one graph satisfying P? The approach to this question is done by using formal languages for specifying families of graphs. We were able to show that typical graph properties can be decided by studying the syntactic monoid of the specification language. But so far, a classification of decidable properties remains wide open.

Creative Commons BY 3.0 DE

Volker Diekert