## Efficient Graph Rewriting and Its ImplementationThis 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 |

255 | |

261 | |

### Other editions - View all

### Common terms and phrases

abstract interpretation abstract machine analysis application predicate attributed graph rewriting bypassing connected enumeration components computation constructor context vertices cut-description defined deleted denoted derivable graphs determined edge labels element Emb,ns embedding descriptions embedding edges evaluation example execution extension failure semantics follows formalism functional languages graph g graph isomorphism graph morphism graph reduction graph rewriting system graphical Hence host graph implementation initial graph inserted instance L(gg label triples labelled subgraph matching labelling function left-hand side lemma Let g LTR(gg mappairs matching algorithm node optimization ordinary rewriting partial handles performed priority queue programmed graph rewriting redex reduction representation result graph rewriting rule right-hand side root rule expression rule set sentential form sequence set of label set of strong slot specification spine static predicates strong V-structures subgraph isomorphism problem svs(gg symmetric graph syntactical translation tree unique vertex labels UV(gg variable wlog