Pattern-Based Graph Abstraction


Rensink, Arend and Zambon, Eduardo (2012) Pattern-Based Graph Abstraction. In: International Conference on Graph Transformation, ICGT 2012, 24-29 September 2012, Bremen, Germany (pp. pp. 66-80).

[img] PDF
Restricted to UT campus only
: Request a copy
Abstract:We present a new abstraction technique for the exploration 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. This paper shows 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.
Item Type:Conference or Workshop Item
Additional information:Winner of the EATCS Award for Best Paper of ICGT 2012
Copyright:© 2012 Springer
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:
Official URL:
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page