Skip to Main content Skip to Navigation
Reports

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.
Document type :
Reports
Complete list of metadata

https://hal.inria.fr/inria-00074847
Contributor : Rapport de Recherche Inria <>
Submitted on : Wednesday, May 24, 2006 - 4:34:04 PM
Last modification on : Friday, May 25, 2018 - 12:02:05 PM
Long-term archiving on: : Tuesday, April 12, 2011 - 7:41:48 PM

Identifiers

  • 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⟩

Share

Metrics

Record views

224

Files downloads

100