Results 1 to 10 of about 251 (176)
Addressing Machines as models of lambda-calculus [PDF]
Logical Methods in Computer Science, 2022 Turing machines and register machines have been used for decades in theoretical computer science as abstract models of computation. Also the $\lambda$-calculus has played a central role in this domain as it allows to focus on the notion of functional ...
Giuseppe Della Penna +2 more
doaj +4 more sources
Asymptotically almost all \lambda-terms are strongly normalizing [PDF]
Logical Methods in Computer Science, 2013 We present quantitative analysis of various (syntactic and behavioral) properties of random \lambda-terms. Our main results are that asymptotically all the terms are strongly normalizing and that any fixed closed term almost never appears in a random ...
René David +5 more
doaj +1 more source
Encoding the Factorisation Calculus [PDF]
Electronic Proceedings in Theoretical Computer Science, 2015 Jay and Given-Wilson have recently introduced the Factorisation (or SF-) calculus as a minimal fundamental model of intensional computation. It is a combinatory calculus containing a special combinator, F, which is able to examine the internal structure ...
Reuben N. S. Rowe
doaj +1 more source
RPO, Second-order Contexts, and Lambda-calculus [PDF]
Logical Methods in Computer Science, 2009 First, we extend Leifer-Milner RPO theory, by giving general conditions to obtain IPO labelled transition systems (and bisimilarities) with a reduced set of transitions, and possibly finitely branching.
Pietro Di Gianantonio +2 more
doaj +1 more source
Mixin Composition Synthesis based on Intersection Types [PDF]
Logical Methods in Computer Science, 2018 We present a method for synthesizing compositions of mixins using type inhabitation in intersection types. First, recursively defined classes and mixins, which are functions over classes, are expressed as terms in a lambda calculus with records ...
Jan Bessai +5 more
doaj +1 more source
Combinatory Logic and Lambda Calculus Are Equal, Algebraically [PDF]
, 2023 It is well-known that extensional lambda calculus is equivalent to extensional combinatory logic. In this paper we describe a formalisation of this fact in Cubical Agda.
Végh, Tamás +3 more
core +1 more source
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
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
Binary Lambda Calculus and Combinatory Logic [PDF]
, 2006 We introduce binary representations of both lambda calculus and combinatory logic terms, and demonstrate their simplicity by providing very compact parser-interpreters for these binary languages.
John Tromp, Tromp, John
core +1 more source