Abstract Graph Transformation

Arend Rensink, D.S. Distefano

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

    40 Citations (Scopus)

    Abstract

    Graphs may be used as representations of system states in operational semantics and model checking; in the latter context, they are being investigated as an alternative to bit vectors. The corresponding transitions are obtained as derivations from graph production rules. In this paper we propose an abstraction technique in this framework: the state graphs are contracted by collecting nodes that are sufficiently similar (resulting in smaller states and a finite state space) and the application of the graph production rules is lifted to this abstract level. Since graph abstractions and rule applications can all be computed completely automatically, we believe that this can be the core of a practically feasible technique for software model checking.
    Original languageEnglish
    Title of host publicationProceedings of the Third International Workshop on Software Verification and Validation (SVV 2005)
    EditorsS. Mukhopadhyay, A. Roychoudhury, Z. Yang
    PublisherElsevier
    Pages39-59
    Number of pages21
    ISBN (Print)1571-0661
    DOIs
    Publication statusPublished - May 2006
    Event3rd International Workshop on Software Verification and Validation, SVV 2005 - Manchester, United Kingdom
    Duration: 31 Oct 200531 Oct 2005
    Conference number: 3

    Publication series

    NameElectronic Notes in Theoretical Computer Science
    PublisherElsevier
    Volume157
    ISSN (Print)1571-0661
    ISSN (Electronic)1571-0661

    Conference

    Conference3rd International Workshop on Software Verification and Validation, SVV 2005
    Abbreviated titleSVV
    CountryUnited Kingdom
    CityManchester
    Period31/10/0531/10/05

    Keywords

    • Graph transformation
    • Software model checking
    • Abstract interpretation

    Fingerprint Dive into the research topics of 'Abstract Graph Transformation'. Together they form a unique fingerprint.

  • Cite this

    Rensink, A., & Distefano, D. S. (2006). Abstract Graph Transformation. In S. Mukhopadhyay, A. Roychoudhury, & Z. Yang (Eds.), Proceedings of the Third International Workshop on Software Verification and Validation (SVV 2005) (pp. 39-59). (Electronic Notes in Theoretical Computer Science; Vol. 157). Elsevier. https://doi.org/10.1016/j.entcs.2006.01.022