Hostname: page-component-745bb68f8f-cphqk Total loading time: 0 Render date: 2025-01-26T03:53:18.192Z Has data issue: false hasContentIssue false
  • English
  • Français

On combinatory complete sets of proper combinators

Published online by Cambridge University Press:  01 November 1997

SABINE BRODA  and
LUÍS DAMAS
SABINE BRODA
Affiliation:
DCC & LIACC, Universidade do Porto, R. do Campo Alegre 823, 4150 Porto, Portugal (e-mail: {sbb,luis}@ncc.up.pt)
LUÍS DAMAS
Affiliation:
DCC & LIACC, Universidade do Porto, R. do Campo Alegre 823, 4150 Porto, Portugal (e-mail: {sbb,luis}@ncc.up.pt)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

A combinatory system (or equivalently the set of its basic combinators) is called combinatorially complete for a functional system, if any member of the latter can be defined by an entity of the former system. In this paper the decision problem of combinatory completeness for finite sets of proper combinators is studied for three subsystems of the pure lambda calculus. Precise characterizations of proper combinator bases for the linear and the affine λ-calculus are given, and the respective decision problems are shown to be decidable. Furthermore, it is determined which extensions with proper combinators of bases for the linear λ-calculus are combinatorially complete for the λI-calculus.

Type
Research Article
Information
Journal of Functional Programming , Volume 7 , Issue 6 , November 1997 , pp. 593 - 612
Copyright
© 1997 Cambridge University Press
Submit a response

Discussions

No Discussions have been published for this article.