Results 11 to 20 of about 307 (171)
Functional completeness of the mixed λ-calculus and combinatory logic [PDF]
Theoretical Computer Science, 1990 The authors present a two-level version of combinatory logic and lambda calculus for distinguishing between early and late binding times, i.e. compile-time and run-time computations. In this paper, which is an extension of a previous one by the same authors, the two-level lambda calculus is enriched by a new combinator, \(\Psi\), which makes the ...
Hanne Riis Nielson, Flemming Nielson
openaire +4 more sources
On the Complexity of the Standard Translation of Lambda Calculus into Combinatory Logic [PDF]
Reports on Mathematical Logic, 2018 We investigate the complexity of the standard translation of lambda calculus into combinatory logic. The main result shows that the asymptotic growth rate of the size of a translated term is Θ(n3) in worst-case, where n denotes the size of the lambda ...
Lachowski, Łukasz
openaire +6 more sources
COMBINATORY LOGIC AND $ lambda $-CALCULUS FOR CLASSICAL LOGIC
COMBINATORY LOGIC AND $ lambda $-CALCULUS FOR CLASSICAL LOGICSince Griffin's work in 1990, classical logic has been an attractive target for extracting computational contents. However, the classical principle used in Griffin's type system is the double-negation-elimination rule, which prevents one to analyze the intuitionistic part and the purely classical part separately. By formulating a calculus with $ mathrm{
馬場, 謙介 +5 more
openaire +2 more sources
Compilation of combinatory reduction systems [PDF]
, 1993 Combinatory Reduction Systems generalise Term Rewriting Systems. They are powerful enough to express β-reduction of λ-calculus as a single rewrite rule. The additional expressive power has its price — CRSs are much harder to implement than ordinary TRSs.
Stefan Kahrs, Kahrs, Stefan
core +1 more source
NP-Completeness of Combinator Optimisation Problem [PDF]
, 1995 We consider a deterministic rewrite system for combinatory logic over combinators S, K, I, B, C, S’, B’ and C’. Terms will be represented by graphs so that reduction of a duplicator will cause the duplicated to be "shared" rather than copied.
Rayward-Smith, V. J. +2 more
core +1 more source
Reduction in a linear lambda-calculus with applications to operational semantics [PDF]
, 2005 We study beta-reduction in a linear lambda-calculus derived from Abramsky's linear combinatory algebras. Reductions are classified depending on whether the redex is in the computationally active part of a term ("surface" reductions) or whether it is ...
Simpson, Alexander, Alex Simpson
core +1 more source
A theorem proving framework for the formal verification of Web Services Composition [PDF]
, 2011 We present a rigorous framework for the composition of Web Services within a higher order logic theorem prover. Our approach is based on the proofs-as-processes paradigm that enables inference rules of Classical Linear Logic (CLL) to be translated into ...
Petros Papapanagiotou +3 more
core +1 more source
The categorical multi-combinator machine - cmcm [PDF]
, 1992 Implementations of functional programming languages can take a number of different forms, and many different machines have been developed for this purpose. This paper introduces another abstract machine, the Categorical Multi-Combinator Machine (CMCM). A
Lins, Rafael D. +3 more
core +1 more source
Counting Terms in the Binary Lambda Calculus [PDF]
, 2014 International audienceIn a paper entitled Binary lambda calculus and combinatory logic, John Tromp presents a simple way of encoding lambda calculus terms as binary sequences.
Grygiel, Katarzyna, Lescanne, Pierre
core +4 more sources
lambda!-calculus, Intersection Types, and Involutions [PDF]
, 2019 Abramsky’s affine combinatory algebras are models of affine combinatory logic, which refines standard combinatory logic in the direction of Linear Logic.
Di Gianantonio P. +14 more
core +1 more source