Incremental pattern matching for regular expressions

Arash Jalali, A.H. Ghamarian, Arend Rensink

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

    1 Citation (Scopus)
    40 Downloads (Pure)

    Abstract

    Graph pattern matching lies at the heart of any graph transformation-based system. Incremental pattern matching is one approach proposed for reducingthe overall cost of pattern matching over successive transformations by preserving the matches that stay relevant after a rule application. An important issue in any matching scheme, is the ability to properly and consistently deal with various facilities that add to the expressiveness of a GT-tool’s rule language. One such feature is the support for regular path expressions, which would let two nodes to be consideredas a “match‿, if a certain path of edges exists between them. In this paper, the incorporation of regular expression support into incremental pattern matching is discussed within the context of the GROOVE tool set. This includes laying down a formal foundation for incremental pattern matching for regular expressions which is then used to justify the extension proposed to add regular expression support to a well-known pattern matching algorithm.
    Original languageEnglish
    Title of host publication11th International Workshop on Graph Transformation and Visual Modeling Techniques, GTVMT 2012
    EditorsAndrew Fish, Leen Lambers
    Place of PublicationBerlin
    PublisherEuropean Association for Software Science and Technology
    Pages736:1-736:12
    Number of pages12
    Publication statusPublished - Mar 2012

    Publication series

    NameElectronic Communications of the EASST
    PublisherEuropean Association for Software Science and Technology
    Volume47
    ISSN (Print)1863-2122
    ISSN (Electronic)1863-2122

    Keywords

    • Graph transformation
    • Incremental pattern matching
    • Regular expressions
    • State Space Exploration
    • Incremental matching
    • Path matching

    Fingerprint Dive into the research topics of 'Incremental pattern matching for regular expressions'. Together they form a unique fingerprint.

  • Cite this

    Jalali, A., Ghamarian, A. H., & Rensink, A. (2012). Incremental pattern matching for regular expressions. In A. Fish, & L. Lambers (Eds.), 11th International Workshop on Graph Transformation and Visual Modeling Techniques, GTVMT 2012 (pp. 736:1-736:12). (Electronic Communications of the EASST; Vol. 47). Berlin: European Association for Software Science and Technology.