2012 | OriginalPaper | Buchkapitel
Pattern-Based Graph Abstraction
verfasst von : Arend Rensink, Eduardo Zambon
Erschienen in: Graph Transformations
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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.