A reformulation of matrix graph grammars with Boolean complexes

MaRDI QIDQ2380228zbMATH OpenFDO

Authors Pedro Pablo Pérez Velasco, Juan de Lara

Publication date 26 March 2010

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/228809, http://www.emis.de/journals/EJC/Volume_16/Abstracts/v16i1r73.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Mathematics Subject Classification ID

Graph theory (05C99) Dynamical systems involving maps of trees and graphs (37E25) Grammars and rewriting systems (68Q42) Graph theory (including graph drawing) in computer science (68R10) Graph theory (educational aspects) (97K30)

Review text

Summary: 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).

Recommendations

• Matrix Graph Grammars with Application Conditions
• Parsing by matrix multiplication generalized to Boolean grammars
• Refining the nonterminal complexity of graph-controlled, programmed, and matrix grammars
• scientific article; zbMATH DE number 3885330
• scientific article; zbMATH DE number 3872712
• Linear graph grammars: Power and complexity
• Simple matrix grammars and their leftmost variants
• The complexity of Szilard languages of matrix grammars revisited
• scientific article; zbMATH DE number 3852433
• On the computational completeness of matrix simple semi-conditional grammars

Cited in

(3)

• Using matrix graph grammars for the analysis of behavioural specifications: sequential and parallel independence
• Matrix Approach to Graph Transformation: Matching and Sequences
• Matrix Graph Grammars with Application Conditions

This page was built for publication: A reformulation of matrix graph grammars with Boolean complexes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2380228)