Church-Rosser theorem for a rewriting system on categorial combinators

Abstract

This paper develops the Church-Rosser theorem for the rewriting system CCLβ on type-free categorial combinators introduced by Curien. The system CCLβ is not confluent. However we show that there are various sets D of categorical combinator terms such that each D satisfies the following two conditions: (1) D is closed under reduction by CCLβ; (2) CCLβ is confluent on D. Moreover we examine the relation among these sets. © 1989.