ISBN 9783843918817

978-3-8439-1881-7, Reihe Informatik

Christoph Blume
Graph Automata and Their Application to the Verification of Dynamic Systems

252 Seiten, Dissertation Universität Duisburg-Essen (2014), Hardcover, B5

Zusammenfassung / Abstract

Graph transformation systems have a wide range of applications. Many concurrent and distributed systems – especially those with a dynamically evolving topology – can be naturally modelled by graphs and graph transformation systems. However, these approaches often introduce an additional level of complexity compared to rule-based systems where states have either a word or tree structure. But since the latter structures have a well-established theory which can be used for several verification techniques, it is natural to ask for an adaption to the setting of graph-like structures. Especially the regular word and tree languages have been studied with great success.

The aim of this thesis is to adapt verification techniques based on formal languages to the graph transformation setting and combine them with results from graph theory. For this purpose recognizable graph languages, which have been introduced by Courcelle, are studied in terms of graph automata. Beside the theoretical aspect of this work, a prototype implementation of a tool suite for creating and manipulating graph automaton, called RAVEN, is introduced.