×

Confluence of indirection reductions in graph rewrite systems. (English) Zbl 0661.68094

The aim of this paper is to show that the indirection graph rewrite systems are confluent, i.e., if G \(\Rightarrow^* G_ 1\) and G \(\Rightarrow^* G_ 2\) for some indirection graphs G, \(G_ 1\) and \(G_ 2\), then there exist isomorphic indirection graphs \(G_ 1'\) and \(G_ 2'\) such that \(G_ 1 \Rightarrow^* G_ 1'\) and \(G_ 2 \Rightarrow^* G_ 2'.\)
To show this, in Section 3 the author introduces equivalence relations on the sets of nodes and arcs of an indirection graph and derives a number of properties of these.
The results of Section 3 are used in Section 4 in order to show that the indirection graph rewrite systems are confluent.
Reviewer: F.-L.Tiplea

MSC:

68T15 Theorem proving (deduction, resolution, etc.) (MSC2010)
68Q45 Formal languages and automata
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ehrig, H., Introduction to the algebraic theory of graph grammars: A survey, (Claus, V.; Ehrig, H.; Rozenberg, G., Graph Grammars and Their Application to Computer Science and Biology, Vol. 73 (1979), Springer: Springer Berlin), 1-69, Lecture Notes in Computer Science
[2] Ehrig, H.; Rosen, B. K., The mathematics of record handling, SIAM J. Comput., 9, 411-469 (1980) · Zbl 0455.68021
[3] Peyton Jones, S. L., The Implementation of Functional Programming Languages (1987), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0712.68017
[4] Rosen, B. K., Tree-manipulating systems and Church-Rosser theorems, J. Assoc. Comput. Mach., 20, 160-187 (1973) · Zbl 0267.68013
[5] Turner, D. A., A new implementation technique for applicative languages, Software—Practice & Experience, 9, 31-49 (1979) · Zbl 0386.68009
[6] Van den Broek, P. M.; Van der Hoeven, G. F., Indirection Reduction and Garbage Collection in Graph Rewrite Systems, Internal Memorandum (1988), Dept. of Computer Science, Twente Univ: Dept. of Computer Science, Twente Univ The Netherlands, to appear
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.