Abstract | ||
---|---|---|
Pattern matching plays a central role in graph transformations as a key technology for computing local contexts in which transformation rules are to be applied. Incremental matching techniques offer a performance advantage over the search-based approach, in a number of scenarios including on-the-fly model synchronization, model simulation, view maintenance, well-formedness checking and state space traversal [1,2]. However, the incremental computation of transitive closure in graph pattern matching has started to be investigated only recently [3]. In this paper, we propose multiple algorithms for the efficient computation of generalized transitive closures. As such, our solutions are capable of computing reachability regions defined by simple graph edges as well as complex binary relationships defined by graph patterns, that may be used in a wide spectrum of modeling problems. We also report on experimental evaluation of our prototypical implementation, carried out within the context of a stochastic system simulation case study. |
Year | DOI | Venue |
---|---|---|
2012 | 10.1007/978-3-642-33654-6_26 | ICGT |
Keywords | Field | DocType |
generalized transitive closure,model simulation,graph pattern,incremental matching technique,incremental computation,graph transformation,simple graph edge,efficient computation,pattern matching,graph pattern matching,incremental pattern | Discrete mathematics,Combinatorics,Transitive reduction,Computer science,Theoretical computer science,Reachability,Null graph,Graph rewriting,Transitive closure,Dependency graph,Pattern matching,Voltage graph | Conference |
Citations | PageRank | References |
10 | 0.52 | 26 |
Authors | ||
5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Gábor Bergmann | 1 | 404 | 27.09 |
István Ráth | 2 | 554 | 34.24 |
Tamás Szabó | 3 | 77 | 12.48 |
Paolo Torrini | 4 | 118 | 9.95 |
Dániel Varró | 5 | 1682 | 118.10 |