A rewriting calculus for cyclic higher-order term graphs

Clara Bertolissi 1 Paolo Baldan 2 Horatiu Cirstea 1 Claude Kirchner 1
1 PROTHEO - Constraints, automatic deduction and software properties proofs
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : Introduced at the end of the nineties, the Rewriting Calculus (rho-calculus, for short) is a simple calculus that fully integrates term-rewriting and lambda-calculus. The rewrite rules, acting as elaborated abstractions, their application and the obtained structured results are first class objects of the calculus. The evaluation mechanism, generalizing beta-reduction, strongly relies on term matching in various theories. In this paper we propose an extension of the rho-calculus, handling graph like structures rather than simple terms. The transformations are performed by explicit application of rewrite rules as first class entities. The possibility of expressing sharing and cycles allows one to represent and compute over regular infinite entities. The calculus over terms is naturally generalized by using unification constraints in addition to the standard rho-calculus matching constraints. This therefore provides us with the basics for a natural extension of an explicit substitution calculus to term graphs. Several examples illustrating the introduced concepts are given.
Type de document :
Communication dans un congrès
Maribel Fernandez. 2nd International Workshop on Term Graph Rewriting - TERMGRAPH'2004, Oct 2004, Rome, Italy, 20 p, 2004, Electronic Notes in Theoretical Computer Science
Liste complète des métadonnées

https://hal.inria.fr/inria-00100095
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 10:14:05
Dernière modification le : jeudi 11 janvier 2018 - 06:19:57

Identifiants

  • HAL Id : inria-00100095, version 1

Collections

Citation

Clara Bertolissi, Paolo Baldan, Horatiu Cirstea, Claude Kirchner. A rewriting calculus for cyclic higher-order term graphs. Maribel Fernandez. 2nd International Workshop on Term Graph Rewriting - TERMGRAPH'2004, Oct 2004, Rome, Italy, 20 p, 2004, Electronic Notes in Theoretical Computer Science. 〈inria-00100095〉

Partager

Métriques

Consultations de la notice

137