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.
In @cite_7 @cite_1 @cite_17 cyclic term graph rewriting is considered using the algorithmic way. Pointer redirection is limited to global redirection of all edges pointing to the root of a redex by redirecting them to point to the root of the instance of the right-hand side. In @cite_10 , Banach, inspired by features found in implementations of declarative languages, proposed rewrite systems close to ours. We share the same graphs and global redirection of pointers. However, Banach did not discuss local redirections of pointers. We differ also in the way to express rewriting. Rewriting steps in @cite_10 are defined by using the notion of opfibration of a category while our approach is based on double-pushouts.
@cite_10 @cite_1 @cite_7 @cite_17
2092445638 176560628 2048022954 2006468185
Abstract The purpose of the present paper is twofold: Firstly, show that it is possible to rewrite graphs in a way equivalent to, and in fact slightly more powerful than that of Ehrig, Pfender and Schneider (1973), which has, since then, been developed mainly by the Berlin school. Our method consists in using a single push-out of partial morphisms and is described in Section 3. Section 1 is devoted to the elementary definitions concerning graphs and related terms. Section 2 contains the set-theoretic prerequisites for the sequel but the proofs have been moved into an appendix, for easier reading. Secondly, we indicate in Section 4 why this method is not really fit for rewriting graphs that represent collapsed terms (i.e., sharing common subterms) and we introduce pushouts of total functions, which are not morphisms everywhere on their domain. This method is connected to the classical rewriting of the corresponding terms. The adequacy of these new rewriting rules is then tested to prove a local confluence criterion a la Knuth-Bendix (1970) in Section 5, the proof of which turns out to be very short. We address the problem of graph rewriting and narrowing as the underlying operational semantics of rule-based programming languages. We propose new optimal graph rewriting and narrowing strategies in the setting of orthogonal constructor-based graph rewriting systems. For this purpose, we first characterize a subset of graphs, called admissible graphs. A graph is admissible if none of its defined operations belongs to a cycle. We then prove the confluence, as well as the confluence modulo bisimilarity (unraveling), of the admissible graph rewriting relation. Afterwards, we define a sequential graph rewriting strategy by using Antoy’s definitional trees. We show that the resulting strategy computes only needed redexes and develops optimal derivations w.r.t. the number of steps. Finally, we tackle the graph narrowing relation over admissible graphs and propose a sequential narrowing strategy which computes independent solutions and develops shorter derivations than most general graph narrowing. The categorical semantics of (an abstract version of) the general term graph rewriting language DACTL is investigated. The operational semantics is reformulated in order to reveal its universal properties. The technical dissonance between the matchings of left-hand sides of rules to redexes, and the properties of rewrite rules themselves, is taken as the impetus for expressing the core of the model as a Grothendieck opfibration of a category of general rewrites over a base of general rewrite rules. Garbage collection is examined in this framework in order to reconcile the treatment with earlier approaches. It is shown that term rewriting has particularly good garbage-theoretic properties that do not generalise to all cases of graph rewriting and that this has been a stumbling block for aspects of some earlier models for graph rewriting. Several authors have investigated the correspondence between graph rewriting and term rewriting. Almost invariably they have considered only acyclic graphs. Yet cyclic graphs naturally arise from certain optimizations in implementing functional languages. They correspond to infinite terms, and their reductions correspond to transfinite term-reduction sequences, which have recently received detailed attention. We formalize the close correspondence between finitary cyclic graph rewriting and a restricted form of infinitary term rewriting, called rational term rewriting. This subsumes the known relation between finitary acyclic graph rewriting and finitary term rewriting. Surprisingly, the correspondence breaks down for general infinitary rewriting