https://www.dagstuhl.de/21217

May 25 – 28 , 2021, Event 21217

Forschungsaufenthalt "Properties of Graphs Specified by a Regular Language"

Organizer

Volker Diekert (Universität Stuttgart, DE)

For support, please contact

Heike Clemens

Description

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.

Motivation text license
  Creative Commons BY 3.0 DE
  Volker Diekert

Online Publications

We offer several possibilities to publish the results of your event. Please contact publishing(at)dagstuhl.de if you are interested.

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf in the library.