Efficient Graph Rewriting and Its Implementation

Front Cover
Springer Science & Business Media, Jul 14, 1995 - Computers - 266 pages
This book presents two major research results on the fast implementation of graph rewriting systems (GRS). First, it explores the class of so-called UBS-GRS, where the complexity of a rewriting step is linear instead of NP, showing for example that visual programming is possible by UBS graph rewriting. Second, an abstract machine for graph rewriting is defined providing an instruction set sufficient for the execution of GRS.
The basic definitions of GRS in the algorithmic approach are introduced and extended by attribution and control structures to comprise a formalism for an operational specification. The translation of a functional programming language to graph rewriting shows the capabilities of UBS-GRS.
 

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

Introduction
1
12 The Major Flaw of Graph Rewriting Its Complexity
4
13 The Plan of Attack Finding the Gap
5
14 Outline
7
21 Vertices Edges and Labels make a Graph Preliminary Definitions
10
22 Algorithmic Graph Rewriting Systems The Basic Formalism
13
23 An Abstract Machine for Labelled Subgraph Matching
24
24 Summary and Related Work
31
522 Matching Instructions
141
523 Structural Graph Updates
145
524 Evaluation of Embedding Descriptions
146
525 Attribute Evaluation
147
526 Control Instructions
149
531 The Syntax
150
532 The Code Generation Rules
152
54 Improvements by Rule Set Optimization
157

31 Unique Labels Singularities in Derived Graphs
38
312 Unique Edge Labels
43
32 Label Triples Detecting Dead Rules and Saving Memory
47
322 Approximation of the Set of Label Triples
49
33 Strong VStructures The Branching Points
56
331 Strong VStructures and Matching in Constant Time
58
332 Determination of a Bypassing Connected Enumeration
63
333 Conditions for the Introduction of Strong VStructures
65
334 Approximation of the Set of Strong VStructures
81
34 Summary and Related Work
85
41 Attributed Graph Rewriting Systems Extension I
92
411 The Formalism
93
412 Application of the Analyses
99
42 Programmed Graph Rewriting Systems Extension II
101
421 The Syntax
105
422 The Failure Semantics
106
423 The Collection Semantics
110
424 Analysis of Further Control Structures
114
43 Summary and Related Works
117
51 Optimization of the Application Test for Rule Sets
125
52 The Graph Rewriting Environment
136
521 The State of the Core Abstract Machine
138
55 Summary and Related Work
160
61 Aspects of Functional Programming
165
62 Translating Functions to Trees Graph Reduction approaches Graph Rewriting
168
622 Function Definitions as Rewriting Rules
170
623 Translating Expressions
171
624 Translating Function Definitions
176
63 Sharing Graph Reduction Meets Graph Rewriting
181
64 Normal Order Reduction Enforcing a Deterministic Evaluation Order
185
641 A Stack of Spine Pointers
187
642 Deconstruction of the Spine Stack
191
643 Unwinding the Spine
192
65 The Printing Mechanism
197
66 The Translation of Lazy Evaluation is UBS
201
661 A Mandatory Set of Prohibited Strong VStructures
202
662 None of the Prohibited Strong VStructures Occur
206
67 Summary and Related Work
213
7 Conclusions
217
List of Figures and Tables
223
Implementation of a Functional Program
225
References
255
Index
261
Copyright

Other editions - View all

Common terms and phrases

References to this book