Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: A Reformulation of Matrix Graph Grammars with Boolean Complexes. | A Reformulation of Matrix Graph Grammars with Boolean Complexes Pedro Pablo Perez Velasco Juan de Lara Escuela Politecnica Superior Universidad Autonoma de Madrid Spain @ Submitted Jul 16 2008 Accepted Jun 10 2009 Published Jun 19 2009 Mathematics Subject Classifications 05C99 37E25 68R10 97K30 68Q42 Abstract 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 . 1 Introduction Graph transformation 1 2 14 is concerned with the manipulation of graphs by means of rules. Similar to Chomsky grammars for strings a graph grammar is made of a set of rules each having a left and a right hand side graphs LHS and RHS and an initial host graph to which rules are applied. The application of a rule to a host graph is called a derivation step and involves the deletion and addition of nodes and edges .
