Handbook of Graph Grammars and Computing by Graph Transformations : Applications, Languages and Theory

by Ehrig, H.; Engels, G.; Kreowski, H-J; Rozenberg, Grzegorz

• ISBN13: 9789810240202
• ISBN10: 9810240201
• Format: Hardcover
• Copyright: 1999-10-01
• Publisher: World Scientific Pub Co Inc

Summary

Considers applications to functional languages, visual and object-oriented languages, software engineering, mechanical engineering, chemical process engineering, and images. Presents implemented specification languages and tools, and structuring and modularization concepts for specification languages. CD-ROM included. DLC: Graph grammars.

Table of Contents

I Term Rewriting and Functional Languages	1	(103)
Term Graph Rewriting	3	(60)
D. Plump
Introduction	4	(1)
Abstract Reduction Systems	5	(4)
Term Graphs	9	(6)
From Hypergraphs to Term Graphs	9	(3)
Collapsing, Copying and Bisimilarity	12	(3)
Bibliographic Notes	15	(1)
Term Graph Rewriting	15	(8)
Term Rewriting	15	(2)
Term Graph Rewriting	17	(3)
Incorporating Collapsing and Copying	20	(3)
Bibliographic Notes	23	(1)
Completeness	23	(6)
Simulating Arbitrary Term Rewrite Derivations	24	(3)
Graph-Reducibility	27	(2)
Bibliographic Notes	29	(1)
Termination	29	(8)
The Relation to Term Rewriting	29	(2)
Combined Systems	31	(3)
A Recursive Path Order on Term Graphs	34	(3)
Confluence	37	(8)
The Relation to Term Rewriting	38	(3)
Decidability and Combined Systems	41	(2)
Plain Term Graph Rewriting and Confluence Modulo Bisimilarity	43	(2)
Term Graph Narrowing	45	(8)
Term Graph Narrowing	45	(4)
Minimally and Maximally Collapsing Narrowing	49	(3)
Bibliographic Notes	52	(1)
Further Topics	53	(10)
References	54	(9)
Graph Rewriting Aspects of Functional Programming	63	(40)
E. Barendsen
S. Smetsers
Introduction	64	(1)
Term Graphs	65	(2)
Graph Rewriting	67	(5)
Graph Rewriting in Practice	72	(1)
Copying	72	(5)
Copying in Practice	75	(2)
Operational Semantics	77	(12)
Reduction Strategies	77	(3)
Graph Syntax	80	(2)
Operational Semantics	82	(4)
Translating Rewrite Systems	86	(3)
Typing Systems	89	(14)
Standard Typing	89	(4)
Strictness Analysis	93	(4)
Recursive Data Types	97	(2)
Strictness Analysis in Practice	99	(1)
References	100	(3)
II Visual and Object-Oriented Languages	103	(110)
Application of Graph Transformation to Visual Languages	105	(76)
R. Bardol
M. Minas
A. Schurr
G. Taentzer
Introduction	107	(1)
Visual Languages and Environments	108	(9)
Defining the Syntax of Visual Languages	117	(18)
Concrete and Abstract Syntax of Visual Languages	117	(3)
Graph Grammars	120	(2)
Hypergraph Representation of Visual Sentences	122	(7)
Graph Structure Representation of Visual Sentences	129	(6)
Generating Visual Language Editors	135	(15)
Visual Editing Modes	135	(3)
GenGed	138	(6)
DiaGen	144	(6)
Generating Visual Language Parsers	150	(11)
The Visual Language Parsing Problem	150	(4)
Parsing for Context-Free Hypergraph Grammars	154	(2)
Parsing for Context-Free Hypergraph Grammars with Embeddings	156	(2)
Parsing for Layered Graph Grammars	158	(3)
Visual Graph Transformation Languages	161	(10)
The Graph Transformation Language Progres	161	(2)
The Graph Transformation Language Agg	163	(2)
Comparison of Graph Transformation Languages	165	(6)
Conclusions	171	(10)
References	172	(9)
Semantics of Object-Oriented Languages	181	(32)
A. Wagner
M. Gogolla
Introduction	182	(1)
Drafting TROLL light Concepts	183	(2)
Other Representations of TROLL light Descriptions	185	(5)
Representing TROLL light Descriptions with UML	185	(1)
An Algebraic Version of TROLL light Descriptions	186	(2)
Relating TROLL light, UML and the Algebraic Version	188	(2)
Abstract Syntax of TROLL light	190	(4)
Operational Semantics for TROLL light	194	(7)
Conclusion	201	(3)
References	202	(2)
Appendix	204	(1)
Complete Specification	204	(5)
Customer Template	204	(1)
Car Template	204	(1)
Booking Template	205	(1)
Company Template	206	(3)
Basic Graph Transformation Definitions	209	(4)
III Applications to Software Engineering	213	(106)
IPSEN Tools	215	(52)
P. Klein
M. Nagl
A. Schurr
Introduction	217	(3)
Related Work	220	(1)
The IPSEN Meta Environment: An Overview	221	(3)
The IPSEN Architecture	224	(3)
Generating Context-Free Editors	227	(5)
Specifying Context-Free Syntax	228	(2)
The Generation Machinery for Context-Free Editors	230	(2)
Specifying and Generating Environments	232	(31)
Modeling the Syntax of Logical Documents	233	(6)
Refining the Specification	239	(5)
From EBNF to Progres	244	(2)
Modeling the Semantics of Logical Documents	246	(7)
From Progres to an Implementation	253	(7)
The Internal Structure of Logical Documents	260	(3)
Summary	263	(4)
References	264	(3)
Applying Graph Transformations to Database Re-Engineering	267	(20)
J. H. Jahnke
A. Zundorf
Introduction	268	(2)
A Database Re-Engineering (DRE) Sample Scenario	270	(2)
Mapping Data Models with Triple Graph Grammars	272	(1)
Schema Redesign Transformation Rules	273	(5)
Properties of Schema Redesign Transformation Rules	278	(5)
Conclusion and Related Work	283	(4)
References	284	(3)
SESAM: A Hybrid Simulation Formalism Based on Graph Grammar Concepts	287	(20)
K. Schneider
Introduction	288	(1)
Learning through Model Building and Experimentation	289	(2)
Students' Problems with Software Engineering Education	289	(1)
Stimulating Reflection: Simulating Software Projects	290	(1)
Exploratory Modeling	291	(1)
The Hybrid Simulation Formalism	291	(11)
The Entity Relationship Schema: Modeling the Universe of Discourse	292	(2)
Situation Model Graph	294	(1)
Effect Models Capture Dynamics	294	(7)
Intergrating the Models into a Simulation Game Run	301	(1)
Working with the Models	302	(2)
Experience with the SESAM System	302	(1)
Lessons Learned Using the Graph Grammar Formalism	303	(1)
Conclusions	304	(3)
References	305	(2)
OPTIMIX --A Tool for Rewriting and Optimizing Programs	307	(12)
U. Assmann
Introduction	308	(1)
What Users can do with Optimix	309	(1)
An Introduction to Optimix Specifications	310	(6)
Rule Groups in Rewrite Procedures	311	(1)
Type-Checking Rules	312	(2)
Transformation Actions in Rules	314	(2)
Experiences and Conclusion	316	(2)
References	317	(1)
Appendix	318	(1)
The Used Subset of CCMIR	318	(1)
IV Applications to Engineering Disciplines	319	(76)
Graph-Based Product and Process Management in Mechanical Engineering	321	(48)
B. Westfechtel
Introduction	322	(2)
The SUKITS Project	324	(4)
Management System	324	(2)
Management Model	326	(2)
Management Model: Informal Description	328	(12)
Product Management Model	328	(5)
Process Management Model	333	(7)
Management Model: Formal Specification	340	(24)
Product Management Model	340	(11)
Process Management Model	351	(10)
Model Adaptation	361	(3)
Conclusion	364	(5)
References	365	(4)
Graph Transformation Based Integration Tools: Application to Chemical Process Engineering	369	(26)
K. Cremer
S. Gruner
M. Nagl
Development Processes and Changes	371	(3)
Integrators for Chemical Engineering	374	(4)
Available Support and Related Work	378	(2)
Experience in Integrator Construction	380	(1)
Integrator Specification with Graph Grammars	381	(6)
From Specification to Implementation	387	(3)
Summary and Future Work	390	(5)
References	392	(3)
V Applications to Pictures	395	(90)
Picture Generation by Collage Grammars	397	(62)
F. Drewes
H.-J. Kreowski
Introduction	398	(1)
Collage Grammars	399	(6)
Collages and Collage Grammars	400	(3)
Proper Collage Grammars	403	(2)
Variations and Extensions	405	(5)
Context-Freeness	410	(3)
The Context-Freeness Lemma	411	(1)
Derivation Trees	411	(1)
Context-Free Collage Languages as Fixed Points	412	(1)
Necessary Conditions for Context-Freeness	413	(9)
The Number of Parts of Collages	415	(4)
The Volume of Parts of Collages	419	(3)
Decidability and Undecidability	422	(16)
The Decidability of Compatible Properties	423	(1)
Some Compatible Properties	424	(3)
Grid Collage Grammars	427	(7)
Undecidable Problems	434	(4)
Generation of Self-Affine Fractals	438	(7)
Comparison With Other Methods of Picture Generation	445	(7)
Iterated Function Systems	445	(3)
Chain-Code Picture Languages	448	(4)
Software Systems	452	(1)
Collage-One, Collage-Two, and Collage-VR	452	(1)
The BIZARR Studio	453	(1)
Treebag	453	(1)
Conclusion	453	(6)
References	454	(5)
Deriving Productions from Productions with an Application to Picasso's CEuvre	459	(26)
H. Gottler
Introduction---A Problem from Art Theory	461	(4)
Some Ideas for a Solution to the Problem	465	(2)
Object-Oriented Databases and Graph Grammars	467	(4)
From Graph Grammars to Two-Level Graph Grammars---The Technical Background	471	(6)
Conclusions---Database Design and Two-Level Graph Grammars in the Picasso Project	477	(4)
References	479	(2)
Appendix	481	(1)
A Formal Definition of Two-Level Graph Rewriting	481	(4)
VI Implemented Specification Languages and Tools	485	(120)
The Progres Approach: Language and Environment	487	(64)
A. Schurr
A. J. Winter
A. Zundorf
Introduction	489	(2)
Specification and VHL Programming Languages	491	(4)
Semiformal Modeling and Formal Specification Languages	491	(1)
Very High Level Query and Programming Languages	492	(2)
Compiler Compiler and Graph Transformation (Meta) Tools	494	(1)
Graph Schemata and Derived Graph Properties	495	(10)
The Running Example and DIANE Graphs	495	(2)
Node Classes, Node Types, and Edge Types	497	(2)
Standard Attribute Types and Functions	499	(1)
External Attribute Types and Functions	500	(1)
Intrinsic Node Attributes	501	(2)
Derived Node Attributes and Constraints	503	(2)
Graph Queries and Graph Transformations	505	(17)
Restrictions and Path Declarations	505	(3)
Subgraph Tests and Attribute Conditions	508	(1)
Productions and Attribute Assignments	509	(3)
Advanced Pattern Matching Concepts	512	(3)
Control Structures and Transactions	515	(3)
Consistency Checking with Constraints	518	(4)
Modules and Updatable Graph Views	522	(10)
PROGRES Packages	524	(3)
Specification-in-the-Large with Packages	527	(3)
Graphical Modeling with Updatable Graph Views	530	(2)
The Programming and Prototyping Environment	532	(10)
Basic Components and their Interdependencies	532	(3)
Editing and Analyzing Specifications	535	(3)
Executing and Debugging Specifications	538	(1)
Prototyping	539	(3)
Graph Grammar Engineering	542	(2)
Summary	544	(7)
References	546	(5)
The AGG Approach: Language and Environment	551	(54)
C. Ermel
M. Rudolf
G. Taentzer
Introduction	553	(2)
Agg Language Concepts	555	(15)
Graphs	555	(2)
Attributes	557	(2)
Graph Transformation	559	(7)
Negative Application Conditions	566	(4)
Sample Application: Finding the Shortest Path	570	(7)
Agg Environment	577	(16)
Editing	577	(7)
Interpretation and Debugging	584	(5)
Implementation Issues	589	(4)
Future Developments	593	(6)
Advanced Attribution Features	594	(1)
Control Flow and Structuring	594	(3)
Distribution Issues	597	(2)
Conclusions	599	(6)
References	601	(4)
VII Structuring and Modularization Concepts	605	(86)
Graph Transformation Units and Modules	607	(32)
H. J. Kreowski
S. Kuske
Introduction	608	(1)
Transformation Units	609	(9)
Graph Transformation Approach	610	(1)
Transformation Units	611	(1)
Interleaving Semantics	611	(2)
Graph Class Expressions	613	(1)
Control Conditions	614	(3)
Application Sequences	617	(1)
Shortest Paths---An Example	618	(13)
Informal Description of the Algorithm	619	(1)
Graph Transformation Approach	619	(1)
Specification of the Algorithm	620	(2)
Graphtheoretic Background	622	(3)
Correctness	625	(2)
Complexity	627	(2)
Completing the Proof	629	(2)
Transformation Modules	631	(3)
Formal Parameter Units and Modules	631	(1)
Composition of Modules	632	(1)
Example	632	(2)
Conclusion	634	(5)
References	635	(4)
A View-Based Approach to System Modeling Based on Open Graph Transformation Systems	639	(30)
R. Heckel
H. Ehrig
G. Engels
G. Taentzer
Introduction	641	(1)
Concept of Views and View Integration	642	(3)
Graph Transformation for System Modeling	645	(8)
Views of Open Graph Transformation Systems	653	(4)
Integration of Views	657	(8)
Conclusion	665	(4)
References	667	(2)
Classification and Comparison of Module Concepts for Graph Transformation Systems	669	(22)
R. Heckel
H. Ehrig
G. Engels
G. Taentzer
Introduction	671	(2)
A Sample Modular Specification	673	(5)
What are the Basic Specifications?	678	(1)
Which Relations Between Specifications are Used?	679	(3)
How are Specifications and Relations Combined to Module Architectures?	682	(4)
Summary	686	(5)
References	687	(4)
Index	691