图文法及图像转换计算手册，卷二
1999-10
Penguin
Ehrig, H.; Engels, G.; Kreowski, H. J.
698
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, modeling 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 language 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 as a fundamental computation paradigm where computation includes specification, programming, and implementation. Over the last three decades, graph grammars have developed at a steady pace into a theoretically attractive and important-for-applications research field. Volume 2 of the indispensable Handbook of Graph Grammars and Computing by Graph Transformations considers applications to functional languages, visual and object-oriented languages, software engineering, mechanical engineering, chemical process engineering, and images. It also presents implemented specification languages and tools, and structuring and modularization concepts for specification languages. The contributions have been written in a tutorial/survey style by the top experts in the corresponding areas. This volume is accompanied by a CD-Rom containing implementations of specification environments based on graph transformation systems, and tools whose implementation is based on the use of graph transformation systems.
Ⅰ Term Rewriting and Functional Languages 1 Term Graph Rewriting (D. Plump) 1.1 Introduction 1.2 Abstract Reduction Systems 1.3 Term Graphs 1.3.1 From Hypergraphs to Term Graphs 1.3.2 Collapsing, Copying and Bisimilarity 1.3.3 Bibliographic Notes 1.4 Term Graph Rewriting 1.4.1 Term Rewriting 1.4.2 Term Graph Rewriting 1.4.3 Incorporating Collapsing and Copying 1.4.4 Bibliographic Notes 1.5 Completeness 1.5.1 Simulating Arbitrary Term Rewrite Derivations 1.5.2 Graph-Reducihility 1.5.3 Bibliographic Notes 1.6 Termination 1.6.1 The Relation to Term Rewriting 1.6.2 Combined Systems 1.6.3 A Recursive Path Order on Term Graphs 1.7 Confluence 1.7.1 The Relation to Term Rewriting 1.7.2 Decidability and Combined Systems 1.7.3 Plain Term Graph Rewriting and Confluence Modulo Bisimilarity 1.8 Term Graph Narrowing 1.8.1 Term Graph Narrowing 1.8.2 Minimally and Maximally Collapsing Narrowing 1.8.3 Bibliographic Notes 1.9 Further Topics References 2 Graph Rewriting Aspects of ~nctional Programming (E. Barendsen, S. Smetsers) 2.1 Introduction 2.2 Term Graphs 2.3 Graph Rewriting 2.3.1 Graph Rewriting in Practice 2.4 Copying 2.4.1 Copying in Practice 2.5 Operational Semantics 2.5.1 Reduction Strategies 2.5.2 Graph Syntax 2.5.3 Operational Semantics 2.5.4 Translating Rewrite Systems 2.6 Typing Systems 2.6.1 Standard Typing 2.6.2 Strictness Analysis 2.6.3 Recursive Data Types 2.6.4 Strictness Analysis in Practice ReferencesⅡ Visual and Object-Oriented Languages 3 Application of Graph Transformation to Visual Languages (R. Bardoh], M. Minas, A. Schiirr, G. Taentzer) 3.1 Introduction 3.2 Visual Languages and Environments 3.3 Defining the Syntax of Visual Languages 3.3.1 Concrete and Abstract Syntax of Visual Languages 3.3.2 Graph Grammars 3.3.3 Hypergraph Representation of Visual Sentences 3.3.4 Graph Structure Representation of Visual Sentences 3.4 Generating Visual Language Editors 3.4.1 Visual Editing Modes 3.4.2 GENGED 3.4.3 DIAGEN 3.5 Generating Visual Language Parsers 3.5.1 The Visual Language Parsing Problem 3.5.2 Parsing for Context-Free Hypergraph Grammars 3.5.3 Parsing for Context-Free Hypergraph Grammars with Embeddings 3.5.4 Parsing for Layered Graph Grammars 3.6 Visual Graph Transformation Languages ……Ⅲ Applications to Software EngineeringⅣ Applications to Engineering DisciplinesⅤ Applications to PicturesⅥ Implemented Specification Languages and ToolsIndex
