A Reformulation of Matrix Graph Grammars with Boolean Complexes
Entity
UAM. Departamento de Ingeniería InformáticaPublisher
University of Delaware. Deparment of Mathematical SciencesDate
2009-06-19Citation
Electronic Journal of Combinatorics 16.1 (2009): R73ISSN
1077-8926 (online); 1097-1440 (print)Funded by
This work has been partially sponsored by the Spanish Ministry of Science and Innovation, project METEORIC (TIN2008-02081/TIN).Editor's Version
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v16i1r73Subjects
InformáticaNote
Prior publication in the Electronic Journal of Combinatorics.Rights
© 2009 Pérez, LaraAbstract
Graph transformation is concerned with the manipulation of graphs by means of rules. Graph grammars have been traditionally studied using techniques from category theory. In previous works, we introduced Matrix Graph Grammars (MGG) as a purely algebraic approach for the study of graph dynamics, based on the representation of simple graphs by means of their adjacency matrices.
The observation that, in addition to positive information, a rule implicitly defines negative conditions for its application (edges cannot become dangling, and cannot be added twice as we work with simple digraphs) has led to a representation of graphs as two matrices encoding positive and negative information. Using this representation, we have reformulated the main concepts in MGGs, while we have introduced other new ideas. In particular, we present (i) a new formulation of productions together with an abstraction of them (so called swaps), (ii) the notion of coherence, which checks whether a production sequence can be potentially applied, (iii) the minimal graph enabling the applicability of a sequence, and (iv) the conditions for compatibility of sequences (lack of dangling edges) and G-congruence (whether two sequences have the same minimal initial graph).
Files in this item
Google Scholar:Pérez Velasco, Pedro Pablo
-
Lara Jaramillo, Juan de
This item appears in the following Collection(s)
Related items
Showing items related by title, author, creator and subject.