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)
39 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 languageUndefined
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

  • EWI-22971
  • Graph TransformationIncremental Pattern MatchingRegular Expressions
  • Regular Expressions
  • RETE Algorithm
  • IR-84316
  • State Space Exploration
  • Incremental Matching
  • METIS-296260
  • Path Matching

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.
Jalali, Arash ; Ghamarian, A.H. ; Rensink, Arend. / Incremental pattern matching for regular expressions. 11th International Workshop on Graph Transformation and Visual Modeling Techniques, GTVMT 2012. editor / Andrew Fish ; Leen Lambers. Berlin : European Association for Software Science and Technology, 2012. pp. 736:1-736:12 (Electronic Communications of the EASST).
@inproceedings{437fccb407754fd1b8b24eaea6d189c4,
title = "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.",
keywords = "EWI-22971, Graph TransformationIncremental Pattern MatchingRegular Expressions, Regular Expressions, RETE Algorithm, IR-84316, State Space Exploration, Incremental Matching, METIS-296260, Path Matching",
author = "Arash Jalali and A.H. Ghamarian and Arend Rensink",
year = "2012",
month = "3",
language = "Undefined",
series = "Electronic Communications of the EASST",
publisher = "European Association for Software Science and Technology",
pages = "736:1--736:12",
editor = "Andrew Fish and Leen Lambers",
booktitle = "11th International Workshop on Graph Transformation and Visual Modeling Techniques, GTVMT 2012",

}

Jalali, A, Ghamarian, AH & 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. Electronic Communications of the EASST, vol. 47, European Association for Software Science and Technology, Berlin, pp. 736:1-736:12.

Incremental pattern matching for regular expressions. / Jalali, Arash; Ghamarian, A.H.; Rensink, Arend.

11th International Workshop on Graph Transformation and Visual Modeling Techniques, GTVMT 2012. ed. / Andrew Fish; Leen Lambers. Berlin : European Association for Software Science and Technology, 2012. p. 736:1-736:12 (Electronic Communications of the EASST; Vol. 47).

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

TY - GEN

T1 - Incremental pattern matching for regular expressions

AU - Jalali, Arash

AU - Ghamarian, A.H.

AU - Rensink, Arend

PY - 2012/3

Y1 - 2012/3

N2 - 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.

AB - 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.

KW - EWI-22971

KW - Graph TransformationIncremental Pattern MatchingRegular Expressions

KW - Regular Expressions

KW - RETE Algorithm

KW - IR-84316

KW - State Space Exploration

KW - Incremental Matching

KW - METIS-296260

KW - Path Matching

M3 - Conference contribution

T3 - Electronic Communications of the EASST

SP - 736:1-736:12

BT - 11th International Workshop on Graph Transformation and Visual Modeling Techniques, GTVMT 2012

A2 - Fish, Andrew

A2 - Lambers, Leen

PB - European Association for Software Science and Technology

CY - Berlin

ER -

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