Incremental Pattern Matching in Graph-Based State Space Exploration

A.H. Ghamarian, Arend Rensink, Arash Jalali

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

    6 Citations (Scopus)
    23 Downloads (Pure)


    Graph pattern matching is among the most costly operations in any graph transformation system. Incremental pattern matching aims at reducing this cost by incrementally updating, as opposed to totally recalculating, the possible matches of rules in the graph grammar at each step of the transformation. In this paper an implementation of one such algorithm is discussed with respect to the GROOVE toolset, with a special emphasis put on state space exploration. Specifically, we shall discuss exploration strategies that could better harness the positive aspects of incremental pattern matching in order to gain better performance.
    Original languageUndefined
    Title of host publicationProceedings of the Fourth International Workshop on Graph-Based Tools (GraBaTs 2010)
    EditorsJ. De Lara, D. Varro
    Place of PublicationEnschede
    PublisherEuropean Association for the Study of Science and Technology
    Number of pages12
    Publication statusPublished - 2010
    EventFourth International Workshop on Graph-Based Tools, GraBaTs 2010: Proceedings of the Fourth International Workshop on Graph-Based Tools (GraBaTs 2010) - University of Twente, Enschede, Netherlands
    Duration: 28 Sep 201028 Sep 2010
    Conference number: 4

    Publication series

    NameCTIT Workshop Proceedings
    PublisherCentre for Telematics and Information Technology University of Twente
    NumberWP 10-06
    ISSN (Print)0929-0672
    ISSN (Electronic)0929-0672


    ConferenceFourth International Workshop on Graph-Based Tools, GraBaTs 2010
    Abbreviated titleGraBaTs 2010
    Other28 September 2010


    • EWI-19547
    • Graph Transformation
    • Incremental pattern matching
    • IR-75907
    • METIS-275915

    Cite this