Simplified Reducibility Proofs of Church-Rosser for β- and βη-reduction

Fairouz Kamareddine, Vincent Rahli

Research output: Contribution to journalArticle

Abstract

The simplest proofs of the Church Rosser Property are usually done by the syntactic method of parallel reduction. On the other hand, reducibility is a semantic method which has been used to prove a number of properties in the ?-calculus and is well known to offer on one hand very general proofs which can be applied to a number of instantiations, and on the other hand, to be quite mysterious and inflexible. In this paper, we concentrate on simplifying a semantic method based on reducibility for proving Church-Rosser for both ß- and ß?-reduction. Interestingly, this simplification results in a syntactic method (so the semantic aspect disappears) which is nonetheless projectable into a semantic method. Our contributions are as follows:•We give a simplification of a semantic proof of CR for ß-reduction which unlike some common proofs in the literature, avoids any type machinery and is solely carried out in a completely untyped setting.•We give a new proof of CR for ß?-reduction which is a generalisation of our simple proof for ß-reduction.•Our simplification of the semantic proof results into a syntactic proof which is projectable into a semantic method and can hence be used as a bridge between syntactic and semantic methods. Crown Copyright © 2009.

Original languageEnglish
Pages (from-to)85-101
Number of pages17
JournalElectronic Notes in Theoretical Computer Science
Volume247
DOIs
Publication statusPublished - 4 Aug 2009

Keywords

  • Church-Rosser
  • Parallel reductions
  • Reducibility

Fingerprint Dive into the research topics of 'Simplified Reducibility Proofs of Church-Rosser for β- and βη-reduction'. Together they form a unique fingerprint.

  • Cite this