The Church-Rosser property in dual combinatory logic
Bimbó, Katalin
J. Symbolic Logic, Tome 68 (2003) no. 1, p. 132-152 / Harvested from Project Euclid
Dual combinators emerge from the aim of assigning formulas containing $\leftarrow$ as types to combinators. This paper investigates formally some of the properties of combinatory systems that include both combinators and dual combinators. Although the addition of dual combinators to a combinatory system does not affect the unique decomposition of terms, it turns out that some terms might be redexes in two ways (with a combinator as its head, and with a dual combinator as its head). We prove a general theorem stating that no dual combinatory system possesses the Church-Rosser property. Although the lack of confluence might be problematic in some cases, it is not a problem per se. In particular, we show that no damage is inflicted upon the structurally free logics, the system in which dual combinators first appeared.
Publié le : 2003-03-14
Classification: 
@article{1045861508,
     author = {Bimb\'o, Katalin},
     title = {The Church-Rosser property in dual combinatory logic},
     journal = {J. Symbolic Logic},
     volume = {68},
     number = {1},
     year = {2003},
     pages = { 132-152},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1045861508}
}
Bimbó, Katalin. The Church-Rosser property in dual combinatory logic. J. Symbolic Logic, Tome 68 (2003) no. 1, pp.  132-152. http://gdmltest.u-ga.fr/item/1045861508/