text: We tackle the problem of data-structure rewriting including pointer redirections. We propose two basic rewrite steps: (i) Local Redirection and Replacement steps the aim of which is redirecting specific pointers determined by means of a pattern, as well as adding new information to an existing data ; and (ii) Global Redirection steps which are aimed to redirect all pointers targeting a node towards another one. We define these two rewriting steps following the double pushout approach. We define first the category of graphs we consider and then define rewrite rules as pairs of graph homomorphisms of the form "L R". Unfortunately, inverse pushouts (complement pushouts) are not unique in our setting and pushouts do not always exist. Therefore, we define rewriting steps so that a rewrite rule can always be performed once a matching is found.
  @cite_0: We identify a set of programming constructs ensuring that a programming language based on graph transformation is computationally complete. These constructs are (1) nondeterministic application of a set of graph transformation rules, (2) sequential composition and (3) iteration. This language is minimal in that omitting either sequential composition or iteration results in a computationally incomplete language. By computational completeness we refer to the ability to compute every computable partial function on labelled graphs. Our completeness proof is based on graph transformation programs which encode arbitrary graphs as strings, simulate Turing machines on these strings, and decode the resulting strings back into graphs.
  @cite_15: Graph programs as introduced by Habel and Plump [8] provide a simple yet computationally complete language for computing functions and relations on graphs. We extend this language such that numerical computations on labels can be conveniently expressed. Rather than resorting to some kind of attributed graph transformation, we introduce conditional rule schemata which are instantiated to (conditional) double-pushout rules over ordinary graphs. A guiding principle in our language extension is syntactic and semantic simplicity. As a case study for the use of extended graph programs, we present and analyse two versions of Dijkstra’s shortest path algorithm. The first program consists of just three rule schemata and is easily proved to be correct but can be exponential in the number of rule applications. The second program is a refinement of the first which is essentially deterministic and uses at most a quadratic number of rule applications.
summary: In @cite_0 , Habel and Plump proposed a kernel language for graph transformation. This language has been improved recently in @cite_15 . Basic rules in this framework are of the form @math satisfying some conditions such as the inclusion @math . Unfortunately, our rewrite rules do not fulfill such condition ; particularly when performing local edge redirections. Furthermore, inverse pushouts (or pushout complements) are not unique in our setting which is not the case in @cite_0 @cite_15 .