Graph Transformation Games for Modeling Adverse Conditions

03. Juli 2017, 14:00 , 15:30

Veranstalter:  Christoph Peuser, Universität Oldenburg
Ort:  A02 2-222 (SCARE Raum)

Graph transformation systems are an elegant solution for many modeling problems in computer science. The
system state is modeled as a graph and state changes are rule applications that change the graph. The existing
correctness notions for graph transformation systems, for example by (Pennemann, 2009) or (Poskitt, 2013)
allow proving correctness of a system with respect to given pre- and postconditions.
In this PhD thesis, we will investigate systems under adverse conditions, e.g. systems under the influence of
an unpredictable environment. Such systems will frequently allow the intermittent violation of desired prop-
erties, as long as these properties can be recovered after some time. We propose to model these systems as
games, with the system and its environment as opposing players. The system is correct if it can reestablish
the desired properties despite the environments interference, that is, if there is a winning strategy for the
The goal of the thesis is the investigation of graph transformation games, i.e. games in which the players
moves are applications of graph transformation rules, as a notion of correctness for systems under adverse
conditions. We identify a decidable subclass of these graph transformation games, arising from ordered hy-
peredge replacement grammars. These grammars can be transformed into parity pushdown games, for which
there are existing solutions (Walukiewicz, 2001). The results are to be illustrated with the help of case studies,
for example a telephone system or a railroad system.
Betreuerin: Prof. Dr. Annegret Habel