Graph Passing in Graph Transformation

A.H. Ghamarian, Arend Rensink

    Research output: Book/ReportReportProfessional

    25 Downloads (Pure)

    Abstract

    Graph transformation works under the whole world assumption. Therefore, in realistic systems, both the individual graphs and the set of all such graphs can grow very large. In reactive formalisms such as process algebra, on the other hand, each system is split into smaller components which continually interact; the interactions pass information such as names or locations between components. The state spaces for the separate components are typically much smaller, and much efficiency can be gained by analysing system behaviour on this level. In this paper we present a framework for compositional graph transformation inspired by name-passing calculi, in which (knowledge about) subgraphs can be passed between components. Essentially, we define graph-passing (reactive) component rules and their composition into traditional (reductive) whole-world rules. This extends previous work in which a simpler form of composition was proposed. The main result is a soundness and completeness result for the composition, showing that the transformations induced by the component rules and their whole-world counterparts are equivalent.
    Original languageUndefined
    Place of PublicationEnschede
    PublisherCentre for Telematics and Information Technology (CTIT)
    Number of pages18
    Publication statusPublished - 31 Jan 2012

    Publication series

    NameCTIT Technical Report Series
    PublisherUniversity of Twente, Centre for Telematics and Information Technology
    No.TR-CTIT-12-04
    ISSN (Print)1381-3625

    Keywords

    • Compositionality
    • Graph Transformation
    • FMT-MC: MODEL CHECKING
    • METIS-285115
    • Soundness and Completeness
    • IR-79646
    • EWI-21480

    Cite this

    Ghamarian, A. H., & Rensink, A. (2012). Graph Passing in Graph Transformation. (CTIT Technical Report Series; No. TR-CTIT-12-04). Enschede: Centre for Telematics and Information Technology (CTIT).
    Ghamarian, A.H. ; Rensink, Arend. / Graph Passing in Graph Transformation. Enschede : Centre for Telematics and Information Technology (CTIT), 2012. 18 p. (CTIT Technical Report Series; TR-CTIT-12-04).
    @book{6eba58a03dc248608da58b99cd961a1f,
    title = "Graph Passing in Graph Transformation",
    abstract = "Graph transformation works under the whole world assumption. Therefore, in realistic systems, both the individual graphs and the set of all such graphs can grow very large. In reactive formalisms such as process algebra, on the other hand, each system is split into smaller components which continually interact; the interactions pass information such as names or locations between components. The state spaces for the separate components are typically much smaller, and much efficiency can be gained by analysing system behaviour on this level. In this paper we present a framework for compositional graph transformation inspired by name-passing calculi, in which (knowledge about) subgraphs can be passed between components. Essentially, we define graph-passing (reactive) component rules and their composition into traditional (reductive) whole-world rules. This extends previous work in which a simpler form of composition was proposed. The main result is a soundness and completeness result for the composition, showing that the transformations induced by the component rules and their whole-world counterparts are equivalent.",
    keywords = "Compositionality, Graph Transformation, FMT-MC: MODEL CHECKING, METIS-285115, Soundness and Completeness, IR-79646, EWI-21480",
    author = "A.H. Ghamarian and Arend Rensink",
    year = "2012",
    month = "1",
    day = "31",
    language = "Undefined",
    series = "CTIT Technical Report Series",
    publisher = "Centre for Telematics and Information Technology (CTIT)",
    number = "TR-CTIT-12-04",
    address = "Netherlands",

    }

    Ghamarian, AH & Rensink, A 2012, Graph Passing in Graph Transformation. CTIT Technical Report Series, no. TR-CTIT-12-04, Centre for Telematics and Information Technology (CTIT), Enschede.

    Graph Passing in Graph Transformation. / Ghamarian, A.H.; Rensink, Arend.

    Enschede : Centre for Telematics and Information Technology (CTIT), 2012. 18 p. (CTIT Technical Report Series; No. TR-CTIT-12-04).

    Research output: Book/ReportReportProfessional

    TY - BOOK

    T1 - Graph Passing in Graph Transformation

    AU - Ghamarian, A.H.

    AU - Rensink, Arend

    PY - 2012/1/31

    Y1 - 2012/1/31

    N2 - Graph transformation works under the whole world assumption. Therefore, in realistic systems, both the individual graphs and the set of all such graphs can grow very large. In reactive formalisms such as process algebra, on the other hand, each system is split into smaller components which continually interact; the interactions pass information such as names or locations between components. The state spaces for the separate components are typically much smaller, and much efficiency can be gained by analysing system behaviour on this level. In this paper we present a framework for compositional graph transformation inspired by name-passing calculi, in which (knowledge about) subgraphs can be passed between components. Essentially, we define graph-passing (reactive) component rules and their composition into traditional (reductive) whole-world rules. This extends previous work in which a simpler form of composition was proposed. The main result is a soundness and completeness result for the composition, showing that the transformations induced by the component rules and their whole-world counterparts are equivalent.

    AB - Graph transformation works under the whole world assumption. Therefore, in realistic systems, both the individual graphs and the set of all such graphs can grow very large. In reactive formalisms such as process algebra, on the other hand, each system is split into smaller components which continually interact; the interactions pass information such as names or locations between components. The state spaces for the separate components are typically much smaller, and much efficiency can be gained by analysing system behaviour on this level. In this paper we present a framework for compositional graph transformation inspired by name-passing calculi, in which (knowledge about) subgraphs can be passed between components. Essentially, we define graph-passing (reactive) component rules and their composition into traditional (reductive) whole-world rules. This extends previous work in which a simpler form of composition was proposed. The main result is a soundness and completeness result for the composition, showing that the transformations induced by the component rules and their whole-world counterparts are equivalent.

    KW - Compositionality

    KW - Graph Transformation

    KW - FMT-MC: MODEL CHECKING

    KW - METIS-285115

    KW - Soundness and Completeness

    KW - IR-79646

    KW - EWI-21480

    M3 - Report

    T3 - CTIT Technical Report Series

    BT - Graph Passing in Graph Transformation

    PB - Centre for Telematics and Information Technology (CTIT)

    CY - Enschede

    ER -

    Ghamarian AH, Rensink A. Graph Passing in Graph Transformation. Enschede: Centre for Telematics and Information Technology (CTIT), 2012. 18 p. (CTIT Technical Report Series; TR-CTIT-12-04).