The graph rewriting calculus: confluence and expressiveness - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Lecture Notes in Computer Science Année : 2005

The graph rewriting calculus: confluence and expressiveness

Résumé

Introduced at the end of the nineties, the Rewriting Calculus (rho-calculus, for short) is a simple calculus that uniformly integrates term-rewriting and lambda-calculus. The Rhog has been recently introduced as an extension of the rho-calculus, handling structures with cycles and sharing. The calculus over terms is naturally generalized by using unification constraints in addition to the standard rho-calculus matching constraints. This leads to a term-graph representation in an equational style where terms consist of unordered lists of equations. In this paper we show that the (linear) Rhog is confluent. The proof of this result is quite elaborated, due to the non-termination of the system and to the fact that we work on equivalence classes of terms. We also show that the Rhog can be seen as a generalization of first-order term-graph rewriting, in the sense that for any term-graph rewrite step a corresponding sequence of rewritings can be found in the Rhog.

Domaines

Autre [cs.OH]
Fichier principal
Vignette du fichier
final.pdf (244.6 Ko) Télécharger le fichier
Loading...

Dates et versions

inria-00000744 , version 1 (15-11-2005)

Identifiants

  • HAL Id : inria-00000744 , version 1

Citer

Clara Bertolissi. The graph rewriting calculus: confluence and expressiveness. 9th Italian Conference on Theoretical Computer Science, ICTCS 2005, Oct 2005, Italie, pp.113 - 127. ⟨inria-00000744⟩
78 Consultations
132 Téléchargements

Partager

Gmail Facebook X LinkedIn More