Lecture Notes ni Computer Science Edited by .G Goos and .J Hartmanis 192 .H girhE .M Nagl G. grebnezoR .A dlefnesoR (Eds.) srammarG-hparG dna riehT noitacilppA ot retupmoC ecneicS 3rd lanoitanretnI Workshop ,ainigriV ,notnerraW USA, December 2-6, 6891 I IIIIIIIIIII galreV-regnirpS nilreB grebledieH NewYork London siraP oykoT hTThh D. Barstow W. Brauer R Brinch Hansen D. Gries D. Luckham C. Moler A. Pnueli G. SeegmSIler J. Stoer N. Wirth Editors Hartmut Ehrig Fachbereich 20, Informatik, Technische Universitfit Berlin Franklinstra6e 28/29, 1000 Berlin 10, Federal Republic of Germany Manfred Nagl Lehrstuhl fur Informatik ,111 RWTH Aachen AhornstraBe 55, 5100 Aachen, Federal Republic of Germany Grzegorz Rozenberg Institute of Applied Mathematics and Computer Science University of Leiden P.O. Box 9512, 2300 Leiden, The Netherlands Azriel Rosenfeld Center for Automation Research, University of Maryland College Park, MD 20742-3411, USA CR Subject Classification (1987): E.1, D.2, D.3, F.1, E2, F.4, 5.1 ISBN 3-540-18771-5 Springer-Verlag Berlin Heidelberg New York ISBN 0-387-18771-5 Springer-Verlag New York Berlin Heidelberg This work is tcejbus to copyright. All rights era ,devreser whether the whole ro part of the lairetam si ,denrecnoc yllacificeps eht rights of ,noitalsnart ,gnitnirper esu-er of ,snoitartsulli ,noitaticer ,gnitsacdaorb noitcudorper no smliforcim ro ni other ,syaw dna egarots ni data .sknab noitacilpuD of this noitacilbup ro strap thereof si only dettimrep rednu eht snoisivorp of eht namreG Copyright waL of rebmetpeS ,9 ,5691 in its noisrev of enuJ ,42 ,5891 dna a copyright eef tsum always eb .diap snoitaloiV fall under eht noitucesorp act of eht namreG Copyright .waL © alreV-regnirpS 9 Berlin grebledieH 7891 detnirP ni ynamreG gnitnirP dna binding: suahkcurD ,z.tleB .rtsgreB/hcabsmeH 012345-0413/5412 Preface 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 has 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, A-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 many others. Through the last 20 years the study of graph-grammars has developed at a steady pace into an active research field holding the interest of many researchers of quite different backgrounds from all over the world. This continuing interest has led to three international workshops on graph-grammars and their applications. The first two were held in Bad Honnef and in Osnabruck (Federal Republic of Germany) in 1978 and 1982. The third workshop took place in December 1986 in Warrenton, Virginia, U.S.A. This volume is based on the contributions presented in Warrenton - not all of the papers presented at the meeting appear in this volume and also some papers from this volume were not presented at the workshop. We felt that in this way the field would be better represented. 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. We hope that this collection of papers will provide the reader with an up-to-date overview of current trends in graph-grammars. In particular we hope that the volume will help the "uninitiated" reader to join this fascinating area which on the one hand offers many challenging mathematical problems while on the other hand provides a whole spectrum of potential applications. We are grateful to NSF for financially supporting the workshop and we are very indebted to about 60 participants of the workshop for creating such a scientifically stimulating and socially pleasant week. H. Ehrig, M. Nagl, A. Rosenfeld, G. Rozenberg Table of Contents PART :I Tutorial Introductions Tutorial introduction to the algebraic approach of graph-grammars H. Ehrig May we introduce to you: hyperedge replacement A. Habel and H.-J. Kreowski 15 An introduction to parallel map generating systems A. Lindenmayer 27 Set theoretic approaches to graph-grammars M. Nagl 41 An introduction to the NLC way of rewriting graphs G. Rozenberg 55 Array grammars A. Rosenfeld 67 PART :II Technical Contributions Graph grammar based specification of interconnection structures for massively parallel computation D.A. Bailey and J.E. Cuny 73 Towards distributed graph-grammars .P Boehm, H. Ehrig, U. Hummert, and M. L6we 86 On partially ordered graph-grammars F.J. Brandenburg 99 A representation of graphs by algebraic expressions and its use for graph rewriting systems B. Courcelle 112 On context-free sets of graphs and their monadic second-order theory .B Courcelle 133 IV Restricting the complexity of regular DNLC languages IJ.J. Aalbersberg, .J Engelfriet, and G. Rozenberg 147 Apex graph-grammars J. Engelfriet, G. Leih, and G. Rozenberg 167 Graph-grammar engineering: A software specification method G. Engels, C. Lewerentz, and W. Sch~fer 186 A linguistic formalism for engineering solid modeling P. Fitzhorn 202 Graph-grammars and diagram editing H. G6ttler 216 Graphics and their grammars .L Hess and B.H. Mayoh 232 On network algebras and recursive equations G. Hotz, R. Kolla, and P. Molitor 250 ADA-concurrency specified by graph grammars M. Jackel 262 Basic notions of actor grammars: A graph grammar model for actor computation D. Janssens and G. Rozenberg 280 Embedding rule independent theory of graph grammars .J Jeffs 299 Supporting the software development process with attributed NLC graph grammars S.M. Kaplan, S.K. Goering, and R.H. Campbell 309 Practical applications of precedence graph grammars M. Kaul 326 Is parallelism already concurrency? Part :I Derivations in graph grammars H.-J. Kreowski 343 VII Is parallelism already concurrency? Part 2: Non sequential processes in graph grammars H.-J. Kreowski and A. Wilharm 361 Map OL-systems with edge label control: Comparison of marker and cyclic systems M.J.M. de Boer and A. Lindenmayer 378 From OL and IL map systems to indeterminate and determinate growth in plant morphogenesis J. L~ck and H.B. LUck 393 Fundamentals of edge-label controlled graph grammars M.G. Main and G. Rozenberg 411 Parallelism analysis in rule-based systems using graph grammars D. Moldovan and .F Parisi-Presicce 427 An efficient algorithm for the solution of hierarchical networks of contraints U. Montanari and .F Rossi 440 A software development environment based on graph technology M. Nagl 458 Map OL systems with markers A. Nakamura, A. Lindenmayer, and .K Aizawa 479 Graph rewriting with unification and composition .F Parisi-Presicce, H. Ehrig, and U. Montanari 496 Complexity of pattern generation via planar parallel binary fission/fusion grammars J.W. Carlyle, S.A. Greibach, and A. Paz 515 Applications of L-systems to computer imagery P. Prusinkiewicz 534 Advances in array languages R. Siromoney 549 IJIV Rosenfeld's cycle grammars and kolam G. Siromoney and R. Siromoney 564 Application of graph grammars in music composing systems F. Wankm~ller 580 Boundary NLC and partition controlled graph grammars E. Welzl 593 PART I TUTORIAL INTRODUCTIONS TUTORIAL INTRODUCTION TO THE ALGEBRAIC APPROACH OF GRAPH GRAMMARS Hartmut Ehrig Technical University Berlin April, 1987 ABSTRACT: This tutorial introduction is intended to provide an intuitive understanding of the general format of the graph grammar mechanism underlying the algebraic approach. We point out the essential role of the gluing construction and discuss basic constructions in connection with sequential and parallel independence of derivations and what to do in the case of sequential resp. parallel dependence. 1. GENERAL FORMAT OF PRODUCTIONS AND DIRECT DERIVATIONS 1.1 Productions A production ;Si a paiir of graphs (B1,B2), called left and right hand side respectively, to- gether with designated gluing points K1 of 1B and K2 of B2 which are in bijective correspondence to each other. 1.2 Direct Derivations A direct derivation from a mother graph G to a daughter graph H is obtained in three steps: Step 1: Match the left hand side 1B of the production with a subgraph of the mother graph G and check the gluing condition (see 1.3). Step 2: Consider the left hand side 1B except of its gluing points K1, i.e. B1-K1, and remove it from the mother graph G. The result is a context graph D which still contains the gluing points K1. Step 3: Add the right hand side B2 to the context graph D by gluing together the gluing points K1 of D with corresponding gluing points K2 of B2. The result is the daughter graph H. 1.3 Gluing Condition The boundary points BOUNDARY are those points in 1B (considered as subgraph of G) which are source or target of arcs in G-B1. The gluing points GLUING of 1B are given by KI. The condition BOUNDARY ---~ GLUING is called gluing condition and assures that the context D in step 2 is indeed a graph. 2. EXAMPLE ("Santa Claus going to White House") This example was presented at the workshop (near to the White House) on December 6. The production shows how a Santa Claus cap is replaced by a silk hat. The mother graph G is Santa Claus with his original cap and the daughter graph H Santa Claus with silk hat. eehT production and the graphs G and H are given in 2.1 and 2.2 below: