A Modal-Logic Based Graph Abstraction

J. Bauer, I.B. Boneva, M.E. Kurban, Arend Rensink

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

    14 Citations (Scopus)

    Abstract

    Infinite or very large state spaces often prohibit the successful verification of graph transformation systems. Abstract graph transformation is an approach that tackles this problem by abstracting graphs to abstract graphs of bounded size and by lifting application of productions to abstract graphs. In this work, we present a new framework of abstractions unifying and generalising existing takes on abstract graph transformation. The precision of the abstraction can be adjusted according to the properties to be verified facilitating abstraction refinement. We present a modal logic defined on graphs, which is preserved and reflected by our abstractions. Finally, we demonstrate the usability of the framework by verifying a graph transformation model of a firewall.
    Original languageUndefined
    Title of host publicationInternational Conference on Graph Transformations (ICGT)
    EditorsH Ehrig, R. Heckel, G. Rozenberg, G. Taentzer
    Place of PublicationBerlin
    PublisherSpringer
    Pages321-335
    Number of pages15
    ISBN (Print)978-3-540-87404-1
    DOIs
    Publication statusPublished - 2008

    Publication series

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

    Keywords

    • IR-62461
    • METIS-251183
    • EWI-13439

    Cite this

    Bauer, J., Boneva, I. B., Kurban, M. E., & Rensink, A. (2008). A Modal-Logic Based Graph Abstraction. In H. Ehrig, R. Heckel, G. Rozenberg, & G. Taentzer (Eds.), International Conference on Graph Transformations (ICGT) (pp. 321-335). [10.1007/978-3-540-87405-8_22] (Lecture Notes in Computer Science; Vol. 5214, No. Supplement). Berlin: Springer. https://doi.org/10.1007/978-3-540-87405-8_22