Graph Grammar Verification through Abstraction

Paolo Baldan, Barbara Koenig, Arend Rensink

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademic

    7 Downloads (Pure)

    Abstract

    Until now there have been few contributions concerning the verification of graph grammars, specifically of infinite-state graph grammars. This paper compares two existing approaches, based on abstractions of graph transformation systems. While in the unfolding approach graph grammars are approximated by Petri nets, in the partitioning approach graphs are abstracted according to their local structure. We describe differences and similarities of the two approaches and explain the underlying ideas.
    Original languageEnglish
    Title of host publicationGraph Transformations and Process Algebras for Modeling Distributed and Mobile Systems
    EditorsBarbara König, Ugo Montanari, Philippa Gardner
    PublisherDagstuhl
    Number of pages9
    Publication statusPublished - 2005
    EventDagstuhl Seminar on Graph Transformations and Process Algebras for Modeling Distributed and Mobile Systems 2004 - Schloss Dagstuhl , Wadern, Germany
    Duration: 6 Jun 200511 Jun 2005

    Publication series

    NameDagstuhl Seminar Proceedings
    PublisherDagstuhl
    Volume04241
    ISSN (Print)1862-4405

    Conference

    ConferenceDagstuhl Seminar on Graph Transformations and Process Algebras for Modeling Distributed and Mobile Systems 2004
    CountryGermany
    CityWadern
    Period6/06/0511/06/05

    Fingerprint

    Petri nets

    Keywords

    • Graph Transformation
    • Verification

    Cite this

    Baldan, P., Koenig, B., & Rensink, A. (2005). Graph Grammar Verification through Abstraction. In B. König, U. Montanari, & P. Gardner (Eds.), Graph Transformations and Process Algebras for Modeling Distributed and Mobile Systems (Dagstuhl Seminar Proceedings; Vol. 04241). Dagstuhl.
    Baldan, Paolo ; Koenig, Barbara ; Rensink, Arend. / Graph Grammar Verification through Abstraction. Graph Transformations and Process Algebras for Modeling Distributed and Mobile Systems. editor / Barbara König ; Ugo Montanari ; Philippa Gardner. Dagstuhl, 2005. (Dagstuhl Seminar Proceedings).
    @inproceedings{c90149286e184f7a984ec72c8e32b736,
    title = "Graph Grammar Verification through Abstraction",
    abstract = "Until now there have been few contributions concerning the verification of graph grammars, specifically of infinite-state graph grammars. This paper compares two existing approaches, based on abstractions of graph transformation systems. While in the unfolding approach graph grammars are approximated by Petri nets, in the partitioning approach graphs are abstracted according to their local structure. We describe differences and similarities of the two approaches and explain the underlying ideas.",
    keywords = "Graph Transformation, Verification",
    author = "Paolo Baldan and Barbara Koenig and Arend Rensink",
    year = "2005",
    language = "English",
    series = "Dagstuhl Seminar Proceedings",
    publisher = "Dagstuhl",
    editor = "Barbara K{\"o}nig and Ugo Montanari and Philippa Gardner",
    booktitle = "Graph Transformations and Process Algebras for Modeling Distributed and Mobile Systems",

    }

    Baldan, P, Koenig, B & Rensink, A 2005, Graph Grammar Verification through Abstraction. in B König, U Montanari & P Gardner (eds), Graph Transformations and Process Algebras for Modeling Distributed and Mobile Systems. Dagstuhl Seminar Proceedings, vol. 04241, Dagstuhl, Dagstuhl Seminar on Graph Transformations and Process Algebras for Modeling Distributed and Mobile Systems 2004, Wadern, Germany, 6/06/05.

    Graph Grammar Verification through Abstraction. / Baldan, Paolo; Koenig, Barbara; Rensink, Arend.

    Graph Transformations and Process Algebras for Modeling Distributed and Mobile Systems. ed. / Barbara König; Ugo Montanari; Philippa Gardner. Dagstuhl, 2005. (Dagstuhl Seminar Proceedings; Vol. 04241).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademic

    TY - GEN

    T1 - Graph Grammar Verification through Abstraction

    AU - Baldan, Paolo

    AU - Koenig, Barbara

    AU - Rensink, Arend

    PY - 2005

    Y1 - 2005

    N2 - Until now there have been few contributions concerning the verification of graph grammars, specifically of infinite-state graph grammars. This paper compares two existing approaches, based on abstractions of graph transformation systems. While in the unfolding approach graph grammars are approximated by Petri nets, in the partitioning approach graphs are abstracted according to their local structure. We describe differences and similarities of the two approaches and explain the underlying ideas.

    AB - Until now there have been few contributions concerning the verification of graph grammars, specifically of infinite-state graph grammars. This paper compares two existing approaches, based on abstractions of graph transformation systems. While in the unfolding approach graph grammars are approximated by Petri nets, in the partitioning approach graphs are abstracted according to their local structure. We describe differences and similarities of the two approaches and explain the underlying ideas.

    KW - Graph Transformation

    KW - Verification

    M3 - Conference contribution

    T3 - Dagstuhl Seminar Proceedings

    BT - Graph Transformations and Process Algebras for Modeling Distributed and Mobile Systems

    A2 - König, Barbara

    A2 - Montanari, Ugo

    A2 - Gardner, Philippa

    PB - Dagstuhl

    ER -

    Baldan P, Koenig B, Rensink A. Graph Grammar Verification through Abstraction. In König B, Montanari U, Gardner P, editors, Graph Transformations and Process Algebras for Modeling Distributed and Mobile Systems. Dagstuhl. 2005. (Dagstuhl Seminar Proceedings).