Narzędzia help

Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
first previous next last
cannonical link button


Fundamenta Informaticae

Tytuł artykułu

Solution to the Range Problem for Combinatory Logic

Autorzy Intrigila, B.  Statman, R. 
Treść / Zawartość
Warianty tytułu
Języki publikacji EN
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  
Wydawca IOS Press
Czasopismo Fundamenta Informaticae
Rocznik 2011
Tom Vol. 111, nr 2
Strony 203--222
Opis fizyczny Bibliogr. 10 poz.
autor Intrigila, B.
autor Statman, R.
[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:
[9] H. Rogers, Jr. Theory of Recursive Functions and Effective Computability.MacGraw Hill New York 1967.
[10] TLCA List of Open Problems.URL:
Kolekcja BazTech
Identyfikator YADDA bwmeta1.element.baztech-article-BUS8-0021-0004