Incremental Pattern Matching for Regular Expressions

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.