Solution to the Range Problem for Combinatory Logic

• Autorzy: Intrigila, B. , Statman, R.
• Języki publikacji: EN

Abstrakty

EN

The lambda-theory H is obtained from beta-conversion by identifying all closed unsolvable terms (or, equivalently, termswithout head normal form). The range problemfor the theoryHasks whether a closed term has always (up to equality in H) either an infinite range or a singleton range (that is, it is a constant function). Here we give a solution to a natural version of this problem, giving a positive answer for the theory H restricted to Combinatory Logic. The method of proof applies also to the Lazy lambda-Calculus.

Słowa kluczowe

EN

lambda calculus; combinatory logic; range problem

• Czasopismo: Fundamenta Informaticae
• Rocznik: 2011
• Tom: Vol. 111, nr 2
• Strony: 203-222
• Opis fizyczny: Bibliogr. 10 poz.

Twórcy

autor

Intrigila, B.

autor

Statman, R.

• Dipartimento di Matematica, Universit`a di Roma "Tor Vergata", Rome, Italy,

Bibliografia

• [1] S. Abramsky, The Lazy Lambda Calculus. In Research Topics in Functional Programming, D. Turner, ed. (AddisonWesley) 1990, 65-117.
• [2] H.P. Barendregt, Constructive Proofs of the Range Property in Lambda Calculus, Theoretical Computer Science 121, (1993) 59-69.
• [3] H.P. Barendregt. The Lambda Calculus. Its Syntax and Semantics. North-Holland, 1984.
• [4] M. Bezem, J.W. Klop, R. de Vrijer ("Terese"). Term Rewriting Systems. Cambridge University Press, 2003.
• [5] H.B. Curry, J.R. Hindley, J.P. Seldin. Combinatory logic. II. North-Holland Publishing Company, 1972.
• [6] J. Roger Hindley, B. Lercher, J. P. Seldin. Introduction to Combinatory Logic. Cambridge University Press, 1972.
• [7] B. Intrigila, R. Statman, On Henk Barendregt's Favorite Open Problem. In Reflections on Type Theory, Lambda Calculus, and the Mind. Essays Dedicated to Henk Barendregt on the Occasion of his 60th Birthday, E. Barendsen, H. Geuvers, V. Capretta, M. Niqui (Eds.), Radboud University, 2007.
• [8] A. Polonsky. Announcement September 10th, 2010. The Types Forum: http://lists.seas.upenn.edu/mailman/listinfo/types-list.
• [9] H. Rogers, Jr. Theory of Recursive Functions and Effective Computability.MacGraw Hill New York 1967.
• [10] TLCA List of Open Problems.URL: http://tlca.di.unito.it/opltlca.