Translating Combinatory Reduction Systems into the Rewriting Calculus

Clara Bertolissi 1 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 : The last few years have seen the development of the rewriting calculus (or rho-calculus, RHO) that extends first order term rewriting and lambda-calculus. The integration of these two latter formalisms has been already handled either by enriching first-order rewriting with higher-order capabilities, like in the Combinatory Reduction Systems, or by adding to lambda-calculus algebraic features. The different higher-order rewriting systems and the rewriting calculus share similar concepts and have similar applications, and thus, it seems natural to compare these formalisms. We analyze in this paper the relationship between the Rewriting Calculus and the Combinatory Reduction Systems and we present a translation of CRS-terms and rewrite rules into rho-terms and we show that for any CRS-reduction we have a corresponding rho-reduction.
Type de document :
Communication dans un congrès
4th International Workshop on Rule-Based Programming - RULE 2003, 2003, Valencia, Spain, 2003
Liste complète des métadonnées

https://hal.inria.fr/inria-00107640
Contributeur : Publications Loria <>
Soumis le : jeudi 19 octobre 2006 - 09:03:43
Dernière modification le : jeudi 11 janvier 2018 - 06:19:57
Document(s) archivé(s) le : mercredi 29 mars 2017 - 13:13:15

Identifiants

  • HAL Id : inria-00107640, version 1

Collections

Citation

Clara Bertolissi, Horatiu Cirstea, Claude Kirchner. Translating Combinatory Reduction Systems into the Rewriting Calculus. 4th International Workshop on Rule-Based Programming - RULE 2003, 2003, Valencia, Spain, 2003. 〈inria-00107640〉

Partager

Métriques

Consultations de la notice

206

Téléchargements de fichiers

51