Journal of Symbolic Logic 68 (1):132 - 152 (2003)
|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|
|Keywords||No keywords specified (fix it)|
|Categories||categorize this paper)|
|Through your library||Configure|
Similar books and articles
Katalin Bombó (2005). The Church-Rosser Property in Symmetric Combinatory Logic. Journal of Symbolic Logic 70 (2):536 - 556.
Katalin Bimbó (2003). The Church-Rosser Property in Dual Combinatory Logic. Journal of Symbolic Logic 68 (1):132-152.
Katalin Bimbó (2000). Investigation Into Combinatory Systems with Dual Combinators. Studia Logica 66 (2):285-296.
Katalin Bimbó (2005). The Church-Rosser Property in Symmetric Combinatory Logic. Journal of Symbolic Logic 70 (2):536 - 556.
M. W. Bunder (1988). Arithmetic Based on the Church Numerals in Illative Combinatory Logic. Studia Logica 47 (2):129 - 143.
Kenneth Loewen (1968). The Church Rosser Theorem for Strong Reduction in Combinatory Logic. Notre Dame Journal of Formal Logic 9 (4):299-302.
Katalin Bimbó (2004). Semantics for Dual and Symmetric Combinatory Calculi. Journal of Philosophical Logic 33 (2):125-153.
E. G. K. López-Escobar (1990). Remarks on the Church-Rosser Property. Journal of Symbolic Logic 55 (1):106-112.
C. Barry Jay (1991). Coherence in Category Theory and the Church-Rosser Property. Notre Dame Journal of Formal Logic 33 (1):140-143.
Barkley Rosser (1942). New Sets of Postulates for Combinatory Logics. Journal of Symbolic Logic 7 (1):18-27.
Yuichi Komori, Naosuke Matsuda & Fumika Yamakawa (forthcoming). A Simplified Proof of the Church–Rosser Theorem. Studia Logica:1-9.
J. Roger Hindley (1972). Introduction to Combinatory Logic. Cambridge [Eng.]University Press.
Katalin Bimbó (2012). Combinatory Logic: Pure, Applied, and Typed. Taylor & Francis.
Haskell B. Curry (1958). Combinatory Logic. Amsterdam, North-Holland Pub. Co..
Pierluigi Minari (1999). Theories of Types and Names with Positive Stratified Comprehension. Studia Logica 62 (2):215-242.
Sorry, there are not enough data points to plot this chart.
Added to index2010-08-24
Recent downloads (6 months)0
How can I increase my downloads?