Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

Structure Manipulation

Matrix Approach to Graph Transformation: Matching and Sequences

Pedro Pablo Pérez VelascoContact Information and Juan de LaraContact Information

(1)  Escuela Politécnica Superior, Universidad Autónoma de Madrid,  
Abstract
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.

Contact Information Pedro Pablo Pérez Velasco
Email: pedro.perez@uam.es

Contact Information Juan de Lara
Email: juan.delara@uam.es
Fulltext Preview (Small, Large)
Image of the first page of the fulltext


Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.114 • Server: mpweb04
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)