Graph-Grammars and Their Application to Computer Science

The generic term "graph-grammars" refers to a variety of methods for specifying (possibly infinite) sets of graphs or sets of maps. The area of graph-grammars originated in the late 60s motivated by considerations concerning pattern recognition - since then the list of areas which have interacted with the development of graph-grammars has grown quite impressively. It includes pattern recognition, software specification and development, VLSI layout schemes, data bases, lambda-calculus, analysis of concurrent systems, massively parallel computer architectures, incremental compilers, computer animation, complexity theory, developmental biology, music composition, representation of physical solids, and many others. This volume is based on the contributions presented at the third international workshop on graph-grammars and their applications, held in Warrenton, Virginia, USA in December 1986. Aiming at the best possible representation of the field not all of the papers presented at the meeting appear in this volume and some of the papers from this volume were not presented at the workshop. The volume consists of two parts: Part I presents tutorial introductions to a number of basic graph and map rewriting mechanisms. Part II contains technical contributions. This collection of papers provides the reader with an up-to-date overview of current trends in graph-grammars.