Pattern-Based Graph Abstraction

Arend Rensink, Eduardo Zambon

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    11 Citations (Scopus)
    30 Downloads (Pure)

    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.
    Original languageUndefined
    Title of host publicationInternational Conference on Graph Transformation (ICGT 2012)
    EditorsH Ehrig, G. Engels, H.J. Kreowski, G. Rozenberg
    Place of PublicationBerlin
    PublisherSpringer
    Pages66-80
    Number of pages15
    ISBN (Print)978-3-642-33653-9
    DOIs
    Publication statusPublished - Sep 2012

    Publication series

    NameLecture Notes in Computer Science
    PublisherSpringer Verlag
    Volume7562
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349

    Keywords

    • IR-82080
    • METIS-289725
    • Abstract Interpretation
    • State Space Exploration
    • Graph Transformation
    • EWI-22348
    • Abstraction

    Cite this

    Rensink, A., & Zambon, E. (2012). Pattern-Based Graph Abstraction. In H. Ehrig, G. Engels, H. J. Kreowski, & G. Rozenberg (Eds.), International Conference on Graph Transformation (ICGT 2012) (pp. 66-80). (Lecture Notes in Computer Science; Vol. 7562). Berlin: Springer. https://doi.org/10.1007/978-3-642-33654-6_5