scientific article; zbMATH DE number 3988733
[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.
- Graph-grammars and their application to computer science. 3rd International Workshop, Warrenton, Virginia, USA, December 2-6, 1986
- Interactive graph grammar
- Integration of graph constraints into graph grammars
- Graph grammars according to the type of input and manipulated data: a survey
- Amalgamation of graph transformations: a synchronization mechanism
- A navigational logic for reasoning about graph properties
- Transformation rules with nested application conditions: critical pairs, initial conflicts \& minimality
- Transformation of variants of Petri nets into context-dependent fusion grammars
- An economical transformation of graph grammars
- On the Specification and Verification of Model Transformations
- Attributed Graph Constraints
- Matrix Graph Grammars with Application Conditions
- scientific article; zbMATH DE number 4049103 (Why is no real title available?)
- scientific article; zbMATH DE number 4049108 (Why is no real title available?)
- scientific article; zbMATH DE number 4094845 (Why is no real title available?)
- On relationships between graph L-systems and picture languages. II
- scientific article; zbMATH DE number 1089086 (Why is no real title available?)
- On the interleaving semantics of transformation units -- a step into GRACE
- Attributed elementary programmed graph grammars
- scientific article; zbMATH DE number 820120 (Why is no real title available?)
- scientific article; zbMATH DE number 919847 (Why is no real title available?)
- scientific article; zbMATH DE number 919849 (Why is no real title available?)
- Single pushout transformations of equationally defined graph structures with applications to actor systems
- On the expressive power of algebraic graph grammars with application conditions
- Initial conflicts for transformation rules with nested application conditions
- A Logic of Graph Constraints
- Grammars with Context Conditions and Their Applications
- Multilevel graph grammars
- Symbolic graphs for attributed graph constraints
- Graph grammars, insertion Lie algebras, and quantum field theory
- Reasoning with graph constraints
- Adaptive star grammars and their languages
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)