Treffer: Matrix approach to graph transformation: Matching and sequences

The final publication is available at Springer via http://dx.doi.org/10.1007/11841883_10 ; Proceedings of Third International Conference, ICGT 2006 Natal, Rio Grande do Norte, Brazil, September 17-23, 2006 ; In this work we present our approach to (simple di-)graph transformation based on an algebra of boolean matrices. Rules are represented as boolean matrices for nodes and edges and derivations can be efficiently characterized with boolean operations only. Our objective is to analyze properties inherent to rules themselves (without considering an initial graph), so this information can be calculated at specification time. We present basic results concerning well-formedness of rules and derivations (compatibility), as well as concatenation of rules, the conditions under which they are applicable (coherence) and permutations. We introduce the match, which permits the identification of a grammar rule left hand side inside a graph. We follow a similar approach to the single pushout approach (SPO), where dangling edges are deleted, but we first adapt the rule in order to take into account any deleted edge. To this end, a notation borrowed from functional analysis is used. We study the conditions under which the calculated data at specification time can be used when the match is considered. ; This work has been sponsored by the Spanish Ministry of Science and Education, project TSI2005-08225-C07-06.