Sep 18, 2012: Eduardo Zambon: Pattern-based Graph Abstraction

September 18, 2012Pattern-based Graph Abstraction
Room: Zi 5126Eduardo Zambon

We present a new abstraction technique for the analysis of graph transformation systems with infinite state spaces. This technique is based on "patterns", simple graphs describing structures of interest that should be preserved by the abstraction. Patterns are collected into "pattern graphs", layered graphs that capture the hierarchical composition of smaller patterns into larger ones. Pattern graphs are then abstracted to a finite universe of "pattern shapes" by collapsing equivalent patterns.

In this talk we show how the application of production rules can be lifted to pattern shapes, resulting in an over-approximation of the original system behaviour and thus enabling verification on the abstract level.