This book contains a collection of 37 refereed full papers selected from the contributions presented at the 5th International Workshop on Graph Grammars and Their Applications to Computer Science, held in Williamsburg, Virginia, USA, in November 1994.
The book covers the whole spectrum of methods and techniques for the investigation of the structure of graphs and graph transformations. The papers are divided into nine topical sections on rewriting techniques, specification and semantics, software engineering, algorithms and architectures, concurrency, graph languages, pattern and graphics, structure and logic of graphs, and biology.
Author(s): R. Alberich, P. Burmeister, F. RossellĂł (auth.), Janice Cuny, Hartmut Ehrig, Gregor Engels, Grzegorz Rozenberg (eds.)
Series: Lecture Notes in Computer Science 1073
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 1996
Language: English
Pages: 573
Tags: Mathematical Logic and Formal Languages; Mathematical Logic and Foundations; Symbolic and Algebraic Manipulation; Artificial Intelligence (incl. Robotics); Combinatorics; Pattern Recognition
A partial algebras approach to graph transformation....Pages 1-15
The contractum in algebraic graph rewriting....Pages 16-26
A category-theoretical approach to vertex replacement: The generation of infinite graphs....Pages 27-37
Issues in the practical use of graph rewriting....Pages 38-55
The category of typed graph grammars and its adjunctions with categories of derivations....Pages 56-74
Graph unification and matching....Pages 75-88
On the interleaving semantics of transformation units — A step into GRACE....Pages 89-106
A graph rewriting framework for Statecharts semantics....Pages 107-121
Programmed graph transformations and graph transformation units in GRACE....Pages 122-136
Pragmatic and semantic aspects of a module concept for graph transformation systems....Pages 137-154
Software integration problems and coupling of graph grammar specifications....Pages 155-169
Using attributed flow graph parsing to recognize clichés in programs....Pages 170-184
Reconfiguration Graph Grammar for massively parallel, fault tolerant computers....Pages 185-195
The use of tree transducers to compute translations between graph algebras....Pages 196-210
The bounded degree problem for non-obstructing eNCE graph grammars....Pages 211-224
Process specification and verification....Pages 225-239
An event structure semantics for graph grammars with parallel productions....Pages 240-256
Synchronized composition of graph grammar productions....Pages 257-270
The decomposition of ESM computations....Pages 271-287
Formal relationship between graph grammars and Petri nets....Pages 288-303
Hierarchically distributed graph transformation....Pages 304-320
On edge addition rewrite systems and their relevance to program analysis....Pages 321-335
Graph automata for linear graph languages....Pages 336-350
The obstructions of a minor-closed set of graphs defined by hyperedge replacement can be constructed....Pages 351-367
Concatenation of graphs....Pages 368-382
HRNCE grammars — A hypergraph generating system with an eNCE way of rewriting....Pages 383-396
Node replacement in hypergraphs: Simulation of hyperedge replacement, and decidability of confluence....Pages 397-411
Chain-code pictures and collages generated by hyperedge replacement....Pages 412-427
Transformations of graph grammars....Pages 428-442
Drawing graphs with attribute graph grammars....Pages 443-453
Graph pattern matching in PROGRES....Pages 454-468
A technique for recognizing graphs of bounded treewidth with application to subclasses of partial 2-paths....Pages 469-486
The definition in monadic second-order logic of modular decompositions of ordered graphs....Pages 487-501
Group based graph transformations and hierarchical representations of graphs....Pages 502-520
Integrating lineage and interaction for the visualization of cellular structures....Pages 521-535
Cellworks with cell rewriting and cell packing for plant morphogenesis....Pages 536-549
Subapical bracketed L-systems....Pages 550-564
