Graph grammars originated in the late 60s, motivated by considerations about pattern recognition and compiler construction. Since then the list of areas which have interacted with the development of graph grammars has grown quite impressively. Besides the aforementioned areas it includes software specification and development, VLSI layout schemes, database design, modelling of concurrent systems, massively parallel computer architectures, logic programming, computer animation, developmental biology, music composition, visual languages, and many others. The area of graph grammars and graph transformations generalizes formal langauge theory based on strings and the theory of term rewriting based on trees. As a matter of fact within the area of graph grammars, graph transformation is considered a fundamental programming paradigm where computation includes specification, programming and implementation. Over the last 25-odd years graph grammars have developed at a steady pace into a theoretically attractive and well-motivated research field. In particular, they are now based on very solid foundations, which are presented in this volume. Volume 1 of the "Handbook of Graph Grammars and Computing by Graph Transformations" includes a state-of-the-art presentation of the foundations of all the basic approaches to rule-based graph specification and transformation: algebraic approach, logic approach, node-based rewriting, (hyer)edge-based rewriting, programmed graph rewriting, and 2-structures. The book has been written in a tutorial/survey style to enhance its usefulness.
Author(s): Grzegorz Rozenberg
Year: 1997
Language: English
Pages: 553
(J . ENGELFRIET, G. ROZENBERG)......Page 17
1.1 Introduction......Page 19
1.2.1 Node replacement and the N L C methodology......Page 20
1.2.2 Extensions and variations: the edNCE grammar......Page 25
1.2.3 Graph replacement grammars......Page 30
1.2.4 Bibliographical comments......Page 31
1.3.1 Formal definition of edNCE graph grammars......Page 32
Leftmost derivations......Page 54
Derivation trees......Page 59
1.3.3 Subclasses......Page 71
1.3.4 Normal forms......Page 77
1.4.1 Regular path characterization......Page 84
1.4.2 Logical characterization......Page 88
1.4.3 Handle replacement......Page 95
1.4.4 Graph expressions......Page 97
1.5 Recognition......Page 98
References......Page 104
(F. DREWES, H.-J. KREOWSKI, A. HABEL)......Page 111
2.1 Introduction......Page 113
2.2 Hyperedge replacement grammars......Page 116
2.2.1 Hypergraphs......Page 118
2.2.2 Hyperedge replacement......Page 120
2.2.3 Hyperedge replacement derivations, grammars, and languages......Page 121
2.2.4 Bibliographic notes......Page 125
2.3.1 Context freeness......Page 127
2.3.2 Derivation trees......Page 130
2.3.3 Bibliographic notes......Page 131
2.4.1 A fixed-point theorem......Page 132
2.4.2 A pumping lemma......Page 134
2.4.3 Parikh's theorem......Page 138
2.4.4 Bibliographic notes......Page 139
2.5.1 Graph-generating hyperedge replacement grammars......Page 140
2.5.2 String-generating hyperedge replacement grammars......Page 141
2.5.3 Further results and bibliographic notes......Page 146
2.6.1 Compatible properties......Page 148
2.6.2 Compatible functions......Page 151
2.6.3 Further results and bibliographic notes......Page 154
2.7.1 NP-completeness......Page 157
2.7.2 Two polynomial algorithms......Page 161
2.7.3 Further results and bibliographic notes......Page 170
2.8 Conclusion......Page 171
References......Page 172
(A. CORRADINI, U. MONTANARI, F. ROSSI, H. EHRIG, R. HECKEL, M. LÖWE)......Page 179
3.1 Introduction......Page 181
3.2.1 Graphs, Productions and Derivations......Page 184
Interleaving......Page 188
Explicit Parallelism......Page 190
3.2.3 Embedding of Derivations and Derived Productions......Page 192
Amalgamation......Page 194
Distribution......Page 195
Semantics......Page 196
Control......Page 197
3.3 Graph Transformation Based on the DPO Construction......Page 198
3.4 Independence and Parallelism in the DPO approach......Page 207
3.5 Models of Computation in the DPO Approach......Page 216
3.5.1 The Concrete and Truly Concurrent Models of Computation......Page 217
3.5.2 Requirements for capturing representation independence......Page 224
3.5.3 Towards an equivalence for representation independence......Page 228
3.5.4 The abstract models of computation for a grammar......Page 233
3.6.1 Embedding of Derivations and Derived Productions......Page 236
Amalgamation......Page 240
Distribution......Page 241
3.8 Appendix A: On commutativity of coproducts......Page 244
3.9 Appendix B: Proof of main results of Section 3.5......Page 248
References......Page 256
(H. EHRIG, R. HECKEL, M. KORFF, M. LÖWE, L. RIBEIRO, A. WAGNER, A. CORRADINI)......Page 263
4.1 Introduction......Page 265
4.2.1 Graph Grammars and Derivations in the SPO Approach......Page 266
4.2.2 Historical Roots of the SPO Approach......Page 274
4.3 Main Results in the SPO Approach......Page 275
Interleaving......Page 276
Explicit Parallelism......Page 280
4.3.2 Embedding of Derivations and Derived Productions......Page 284
4.3.3 Amalgamation and Distribution......Page 289
4.4.1 Negative Application Conditions......Page 294
Interleaving......Page 298
Explicit Parallelism......Page 300
4.5 Transformation of More General Structures in the SPO Approach......Page 303
4.5.1 Attributed Graphs......Page 304
4.5.2 Graph Structures and Generalized Graph Structures......Page 308
4.5.3 High-Level Replacement Systems......Page 310
4.6 Comparison of DPO and SPO Approach......Page 312
4.6.1 Graphs, Productions, and Derivations......Page 314
Interleaving......Page 317
Explicit Parallelism......Page 318
4.6.3 Embedding of Derivations and Derived Productions......Page 321
4.6.4 Amalgamation and Distribution......Page 322
4.7 Conclusion......Page 324
References......Page 325
(B. COURCELLE)......Page 329
5.1 Introduction......Page 331
5.2.1 Structures......Page 333
5.2.2 First-order logic......Page 334
5.2.3 Second-order logic......Page 335
5.2.4 Monadic second-order logic......Page 336
5.2.5 Decidability questions......Page 338
5.2.6 Some tools for constructing formulas......Page 340
5.2.7 Transitive closure and path properties......Page 343
5.2.8 Monadic second-order logic without individual variables......Page 347
5.2.9 A worked example: the definition of square grids in MS logic......Page 348
5.3.1 Partial orders......Page 350
5.3.2 Edge set quantifications......Page 351
5.3.3 Hypergraphs......Page 355
5.4.1 Cardinality predicates......Page 356
5.4.2 Linearly ordered structures......Page 358
5.4.3 Finiteness......Page 360
5.5.1 Transductions of relational structures......Page 362
5.5.2 The fundamental property of definable transductions......Page 367
5.5.3 Comparisons of representations of partial orders, graphs and hypergraphs by relational structures......Page 370
5.6.1 Equational sets......Page 372
5.6.2 Graphs with ports and VR sets of graphs......Page 378
5.6.3 Hypergraphs with sources and HR sets of hypergraphs......Page 383
5.7.1 Inductive sets of predicates and recognizable sets......Page 388
5.7.2 Inductivity of monadic second-order predicates......Page 395
5.7.3 Inductively computable functions and a generalization of Parikh's theorem......Page 399
5.7.4 Logical characterizations of recognizability......Page 405
5.8.1 Minors......Page 406
5.8.2 The structure of sets of graphs having decidable monadic theories......Page 412
References......Page 413
(A. EHRENFEUCHT, T. HARJU, G. ROZENBERG)......Page 417
6.1 Introduction......Page 419
6.2.1 Definition of a 2-structure......Page 420
6.2.2 Clans......Page 423
6.2.3 Basic properties of clans......Page 426
6.3.1 Prime clans......Page 427
6.3.2 Quotients......Page 428
6.3.3 Maximal prime clans......Page 432
6.3.4 Special 2-structures......Page 434
6.3.5 The clan decomposition theorem......Page 435
6.3.6 The shape of a 2-structure......Page 437
6.3.8 Clans and sibas......Page 443
6.4.1 Hereditary properties......Page 446
6.4.2 Uniformly non-primitive 2-structures......Page 449
6.5.1 Angular 2-structures......Page 450
6.5.2 T-structures and texts......Page 454
6.6.1 Definition of a labeled 2-structure......Page 458
6.6.2 Substructures, clans and quotients......Page 460
6.7.1 Motivation......Page 463
6.7.2 Group labeled 2-structures......Page 465
6.7.3 Dynamic labeled 2-structures......Page 466
6.7.4 Clans of a dynamic 2-structure......Page 470
6.7.5 Horizons......Page 471
6.8.1 Disjoint union of 2-structures......Page 473
6.8.2 Comparison with grammatical substitution......Page 474
6.8.3 Amalgamated union......Page 475
6.9.1 Quotients of dynamic 2-structures......Page 476
6.9.2 Plane trees......Page 477
6.10.1 Introduction to invariants......Page 485
6.10.2 Free invariants......Page 486
6.10.3 Basic properties of free invariants......Page 488
6.10.4 Invariants on abelian groups......Page 489
References......Page 492
(A. SCHÜRR)......Page 495
7.1.1 Programmed Graph Replacement Systems in Practice......Page 497
7.1.2 Programmed Graph Replacement Systems an Theory......Page 498
7.1.3 Contents of the Contribution......Page 499
7.2 Logic-Based Structure Replacement Systems......Page 500
7.2.1 Structure Schemata and Schema Consistent Structures......Page 501
7.2.2 Substructures with Additional Constraints......Page 508
7.2.3 Schema Preserving Structure Replacement......Page 514
7.2.4 Summary......Page 520
7.3 Programmed Structure Replacement Systems......Page 521
7.3.1 Requirements for Rule Controlling Programs......Page 522
7.3.2 Basic Control Flow Operators......Page 523
7.3.3 Preliminary Definitions......Page 526
7.3.4 A Fixpoint Semantics for Transactions......Page 528
7.3.5 Summary......Page 534
7.4 Context-sensitive Graph Replacement Systems - Overview......Page 535
7.4.1 Context-sensitive Graph Replacement Rules......Page 536
7.4.2 Embedding Rules and Path Expressions......Page 539
7.4.3 Positive and Negative Application Conditions......Page 542
7.5 Programmed Graph Replacement Systems - Overview......Page 546
7.5.1 Declarative Rule Regulation Mechanisms......Page 548
7.5.2 Programming with Imperative Control Structures......Page 550
7.5.3 Programming with Control Flow Graphs......Page 553
7.5.4 Summary......Page 556
References......Page 557
Index......Page 563
