The church-Rosser property in dual combinatory logic

Journal of Symbolic Logic 68 (1):132-152 (2003)
  Copy   BIBTEX

Abstract

Dual combinators emerge from the aim of assigning formulas containing ← 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

Other Versions

No versions found

Links

PhilArchive

    This entry is not archived by us. If you are the author and have permission from the publisher, we recommend that you archive it. Many publishers automatically grant permission to authors to archive pre-prints. By uploading a copy of your work, you will enable us to better index it, making it easier to find.

    Upload a copy of this work     Papers currently archived: 104,599

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

The Church-Rosser Property in Symmetric Combinatory Logic.Katalin Bimbó - 2005 - Journal of Symbolic Logic 70 (2):536 - 556.
Dual Identity Combinators.Katalin Bimbó - 1998 - The Paideia Archive: Twentieth World Congress of Philosophy 8:11-18.
Combinators and structurally free logic.J. Dunn & R. Meyer - 1997 - Logic Journal of the IGPL 5 (4):505-537.
Some results on combinators in the system TRC.Thomas Jech - 1999 - Journal of Symbolic Logic 64 (4):1811-1819.
Combinatory logic with discriminators.John T. Kearns - 1969 - Journal of Symbolic Logic 34 (4):561-575.

Analytics

Added to PP
2009-01-28

Downloads
63 (#366,429)

6 months
11 (#332,550)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Katalin Bimbo
University of Alberta

Citations of this work

Semantics for dual and symmetric combinatory calculi.Katalin Bimbó - 2004 - Journal of Philosophical Logic 33 (2):125-153.
Combinatory logic.Katalin Bimbó - 2009 - Stanford Encyclopedia of Philosophy.

Add more citations

References found in this work

Combinatory Logic.Haskell B. Curry, J. Roger Hindley & Jonathan P. Seldin - 1977 - Journal of Symbolic Logic 42 (1):109-110.
Combinators and structurally free logic.J. Dunn & R. Meyer - 1997 - Logic Journal of the IGPL 5 (4):505-537.
Two extensions of the structurally free logic LC.K. Bimbó & J. Dunn - 1998 - Logic Journal of the IGPL 6 (3):403-424.
Dual combinators bite the dust.R. K. Meyer, K. Bimbó & J. M. Dunn - 1998 - Bulletin of Symbolic Logic 4:463-464.

View all 7 references / Add more references