The Church-rosser theorem in orthogonal combinatory reduction systems

Zurab Khasidashvili 1
1 PARA - Parallélisme
Inria Paris-Rocquencourt
Abstract : We introduce a notion of Combinatory Reduction Systems (CRSs) by extending the notion of Term Rewriting Systems (TRSs) with variable-binding and substitution mechanisms, define orthogonal CRSs (OCRSs) and prove a strict version of the Church-Rosser theorem for all OCRSs. Our notion of OCRSs is almost equivalent to that of Klop, Kennaway and Van Raamsdonk. Different proofs of the Church-Rosser theorem are in Klop and in Van Raamsdonk.
Type de document :
Rapport
[Research Report] RR-1825, INRIA. 1992
Liste complète des métadonnées

https://hal.inria.fr/inria-00074847
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 16:34:04
Dernière modification le : vendredi 25 mai 2018 - 12:02:05
Document(s) archivé(s) le : mardi 12 avril 2011 - 19:41:48

Fichiers

Identifiants

  • HAL Id : inria-00074847, version 1

Collections

Citation

Zurab Khasidashvili. The Church-rosser theorem in orthogonal combinatory reduction systems. [Research Report] RR-1825, INRIA. 1992. 〈inria-00074847〉

Partager

Métriques

Consultations de la notice

194

Téléchargements de fichiers

66