Incremental Pattern Matching in Graph-Based State Space Exploration
Amir Hossein Ghamarian, Arash Jalali, Arend Rensink
Abstract
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.
Topics & Concepts
Computer scienceGraph rewritingGraphMatching (statistics)3-dimensional matchingPattern matchingTheoretical computer scienceTransformation (genetics)Artificial intelligenceAlgorithmData miningMathematicsChemistryBiochemistryGeneStatisticsBipartite graphModel-Driven Software Engineering TechniquesSemantic Web and OntologiesAI-based Problem Solving and Planning