Journal of Symbolic Logic 70 (2):536-556 (2005)

Authors
Katalin Bimbo
University of Alberta
Abstract
Symmetic combinatory logic with the symmetric analogue of a combinatorially complete base is known to lack the Church-Rosser property. We prove a much stronger theorem that no symmetric combinatory logic that contains at least two proper symmetric combinators has the Church-Rosser property. Although the statement of the result looks similar to an earlier one concerning dual combinatory logic, the proof is different because symmetric combinators may form redexes in both left and right associated terms. Perhaps surprisingly, we are also able to show that certain symmetric combinatory logics that include just one particular constant are not confluent. This result clearly sets apart symmetric combinatory logic from dual combinatory logic, since all dual combinatory systems with a single combinator or a single dual combinator are Church-Rosser. Lastly, we prove that a symmetric combinatory logic that contains the fixed point and the one-place identity combinator has the Church-Rosser property.
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI http://projecteuclid.org/euclid.jsl/1120224727
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 55,856
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

The Calculi of Lambda-Conversion.Barkley Rosser - 1941 - Journal of Symbolic Logic 6 (4):171-171.
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.
Semantics for Dual and Symmetric Combinatory Calculi.Katalin Bimbó - 2004 - Journal of Philosophical Logic 33 (2):125-153.

View all 7 references / Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles

The Church-Rosser Property in Symmetric Combinatory Logic.Katalin Bimbó - 2005 - Journal of Symbolic Logic 70 (2):536 - 556.
The Church-Rosser Property in Dual Combinatory Logic.Katalin Bimbó - 2003 - Journal of Symbolic Logic 68 (1):132-152.
Semantics for Dual and Symmetric Combinatory Calculi.Katalin Bimbó - 2004 - Journal of Philosophical Logic 33 (2):125-153.
Analytic Combinatory Calculi and the Elimination of Transitivity.Pierluigi Minari - 2003 - Archive for Mathematical Logic 43 (2):159-191.
The Church Rosser Theorem for Strong Reduction in Combinatory Logic.Kenneth Loewen - 1968 - Notre Dame Journal of Formal Logic 9 (4):299-302.
Combinators and Structurally Free Logic.J. Dunn & R. Meyer - 1997 - Logic Journal of the IGPL 5 (4):505-537.
Introduction to Combinatory Logic.J. Roger Hindley - 1972 - Cambridge University Press.
Compact Bracket Abstraction in Combinatory Logic.Sabine Broda & Luís Damas - 1997 - Journal of Symbolic Logic 62 (3):729-740.
Compact Bracket Abstraction in Combinatory Logic.Sabine Broda & Luis Damas - 1997 - Journal of Symbolic Logic 62 (3):729-740.
Combinatory Logic.Haskell B. Curry - 1958 - Amsterdam: North-Holland Pub. Co..
NP-Completeness of a Combinator Optimization Problem.M. S. Joy & V. J. Rayward-Smith - 1995 - Notre Dame Journal of Formal Logic 36 (2):319-335.

Analytics

Added to PP index
2017-02-21

Total views
7 ( #998,305 of 2,401,758 )

Recent downloads (6 months)
4 ( #198,131 of 2,401,758 )

How can I increase my downloads?

Downloads

My notes