scientific article; zbMATH DE number 3988733

From MaRDI portal
Publication:3751030





[For the entire collection see Zbl 0575.00023.] Various concepts of graph grammars have been developed and applied to several areas in computer science and biology. In each of these concepts it is defined how and under which conditions graph grammar productions can be applied to a given mother graph in order to obtain a derived daughter graph. Usually the application condition is inherent for each specific graph grammar approach and applies in a uniform way to all productions of a graph grammar within this approach. In this paper the authors propose to allow different application conditions for different productions in order to obtain greater flexibility. The approach to graph grammars is the algebraic one in which a production is a quintuple \(p=(B_ 1\leftarrow K\to B_ 2)\), where \(B_ 1\), \(B_ 2\), the left and right-hand side, and K, the interface gluing points, are finite graphs, and \(K\to B_ 1\), \(K\to B_ 2\) are injective graph morphisms, and a direct graph derivation from a graph G to a graph H is a couple of pushouts, \(KB_ 1DG\) and \(KB_ 2DH\). Given a graph grammar and one of its productions p, an application condition A(p) consists of a couple of decidable subsets \(A_ 1(p)\) and \(A_ 2(p)\) of graph morphisms from \(B_ 1\) to G and from \(B_ 2\) to H, respectively. In particular, application conditions are considered which are called concrete context conditions. The authors prove the following containment relations: L(DFGG)\(\subset L(CFGGA)=L(CSGG)\subset L(GG)=L(GGA)\), where CFGG resp. CFGGA is the class of context-free graph grammars (i.e. graph grammars such that the left-hand side consists of one only edge) without resp. with concrete context conditions, CSGG is the class of context sensitive graph grammars, GG resp. GGA is the class of graph grammars without resp. with application conditions, and L(G) is the class of languages generated by G. The authors show how results concerning graph transformations, like Church-Rosser and parallelism results, can be extended from graph grammars without to those with application conditions.




Cited in
(32)








This page was built for publication:

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