The Experts below are selected from a list of 324 Experts worldwide ranked by ideXlab platform
Antonino Salibra - One of the best experts on this subject based on the ideXlab platform.
-
applying universal algebra to Lambda Calculus
Journal of Logic and Computation, 2010Co-Authors: Giulio Manzonetto, Antonino SalibraAbstract:The aim of this article is double. From one side we survey the knowledge we have acquired these last ten years about the lattice of all λ-theories (equational extensions of untyped λ-Calculus) and the models of Lambda Calculus via universal algebra. This includes positive or negative answers to several questions raised in these years as well as several independent results, the state of the art about the long-standing open questions concerning the representability of λ-theories as theories of models, and 26 open problems. On the other side, against the common belief, we show that Lambda Calculus and combinatory logic satisfy interesting algebraic properties. In fact the Stone representation theorem for Boolean algebras can be generalized to combinatory algebras and λ-abstraction algebras. In every combinatory and λ-abstraction algebra, there is a Boolean algebra of central elements (playing the role of idempotent elements in rings). Central elements are used to represent any combinatory and λ-abstraction algebra as a weak Boolean product of directly indecomposable algebras (i.e. algebras that cannot be decomposed as the Cartesian product of two other non-trivial algebras). Central elements are also used to provide applications of the representation theorem to Lambda Calculus. We show that the indecomposable semantics (i.e. the semantics of Lambda Calculus given in terms of models of Lambda Calculus, which are directly indecomposable as combinatory algebras) includes the continuous, stable and strongly stable semantics, and the term models of all semisensible λ-theories. In one of the main results of the article we show that the indecomposable semantics is equationally incomplete, and this incompleteness is as wide as possible.
-
The Sensible Graph Theories of Lambda Calculus
2004Co-Authors: Antonio Bucciarelli, Antonino SalibraAbstract:Sensible Lambda theories are equational extensions of the untyped Lambda-Calculus that equate all the unsolvable Lambda-terms and are closed under derivation. The least sensible Lambda theory is the Lambda theory $\cH$ (generated by equating all the unsolvable terms), while the greatest sensible Lambda theory is the Lambda theory $\cH^*$ (generated by equating terms with the same Böhm tree up to possibly infinite $\eta$-equivalence). A longstanding open problem in Lambda Calculus is whether there exists a non-syntactic model of Lambda Calculus whose equational theory is the least sensible $\gl$-theory $\cH$. A related question is whether, given a class of models, there exist a minimal and maximal sensible Lambda-theory represented by it. In this paper we give a positive answer to this question for the semantics of Lambda Calculus given in terms of graph models (graph semantics, for short). We conjecture that the minimal sensible graph theory (where ``graph theory" means ``Lambda-theory of a graph model") is equal to $\cH$, while in the main result of the paper we characterize the maximal sensible graph theory as the Lambda-theory $\cB$ (generated by equating $\gl$-terms with the same Böhm tree). In fact, we prove that all the equation $M = N$ between solvable Lambda-terms $M$ and $N$, which have different Böhm trees, fail in every graph model. In a further result of the paper we prove the existence of a continuum of different graph models whose equational theories are sensible and strictly included in $\cB$
-
MFCS - The Minimal Graph Model of Lambda Calculus
Mathematical Foundations of Computer Science 2003, 2003Co-Authors: Antonio Bucciarelli, Antonino SalibraAbstract:A longstanding open problem in Lambda-Calculus, raised by G.Plotkin, is whether there exists a continuous model of the untyped Lambda-Calculus whose theory is exactly the beta-theory or the beta-eta-theory. A related question, raised recently by C.Berline, is whether, given a class of Lambda-models, there is a minimal equational theory represented by it.
-
Topological incompleteness and order incompleteness of the Lambda Calculus
ACM Transactions on Computational Logic, 2003Co-Authors: Antonino SalibraAbstract:A model of the untyped Lambda Calculus univocally induces a Lambda theory (i.e., a congruence relation on λ-terms closed under α- and β-conversion) through the kernel congruence relation of the interpretation function. A semantics of Lambda Calculus is (equationally) incomplete if there exists a Lambda theory that is not induced by any model in the semantics. In this article, we introduce a new technique to prove in a uniform way the incompleteness of all denotational semantics of Lambda Calculus that have been proposed so far, including the strongly stable one, whose incompleteness had been conjectured by Bastonero, Gouy and Berline. We apply this technique to prove the incompleteness of any semantics of Lambda Calculus given in terms of partially ordered models with a bottom element. This incompleteness removes the belief that partial orderings with a bottom element are intrinsic to models of the Lambda Calculus, and that the incompleteness of a semantics is only due to the richness of the structure of representable functions. Instead, the incompleteness is also due to the richness of the structure of Lambda theories. Further results of the article are: (i) an incompleteness theorem for partially ordered models with finitely many connected components (= minimal upward and downward closed sets); (ii) an incompleteness theorem for topological models whose topology satisfies a suitable property of connectedness; (iii) a completeness theorem for topological models whose topology is non-trivial and metrizable.
-
The Minimal Graph Model of Lambda Calculus
2003Co-Authors: Antonio Bucciarelli, Antonino SalibraAbstract:A longstanding open problem in Lambda-Calculus, raised by G.Plotkin, is whether there exists a continuous model of the untyped Lambda-Calculus whose theory is exactly the beta-theory or the beta-eta-theory. A related question, raised recently by C.Berline, is whether, given a class of Lambda-models, there is a minimal theory represented by it. In this paper, we give a positive answer to this latter question for the class of graph models à la Plotkin-Scott-Engeler. In particular, we build a graph model in which the equations satisfied are exactly those satisfied in any graph model.
Michel Parigot - One of the best experts on this subject based on the ideXlab platform.
-
FoSSaCS - Spinal Atomic Lambda-Calculus
Lecture Notes in Computer Science, 2020Co-Authors: David Sherratt, Willem Heijltjes, Tom Gundersen, Michel ParigotAbstract:We present the spinal atomic \(\Lambda \)-Calculus, a typed \(\Lambda \)-Calculus with explicit sharing and atomic duplication that achieves spinal full laziness: duplicating only the direct paths between a binder and bound variables is enough for beta reduction to proceed. We show this Calculus is the result of a Curry–Howard style interpretation of a deep-inference proof system, and prove that it has natural properties with respect to the \(\Lambda \)-Calculus: confluence and preservation of strong normalisation.
-
LICS - Atomic Lambda Calculus: A Typed Lambda-Calculus with Explicit Sharing
2013 28th Annual ACM IEEE Symposium on Logic in Computer Science, 2013Co-Authors: Tom Gundersen, Willem Heijltjes, Michel ParigotAbstract:An explicit -- sharing Lambda-Calculus is presented, based on a Curry -- Howard-style interpretation of the deep inference proof formalism. Duplication of subterms during reduction proceeds 'atomically', i.e. on individual constructors, similar to optimal graph reduction in the style of Lamping. The Calculus preserves strong normalisation with respect to the LambdaCalculus, and achieves fully lazy sharing.
-
LPAR - A Proof of Strong Normalisation of the Typed Atomic Lambda-Calculus
Logic for Programming Artificial Intelligence and Reasoning, 2013Co-Authors: Tom Gundersen, Willem Heijltjes, Michel ParigotAbstract:The atomic Lambda-Calculus is a typed Lambda-Calculus with explicit sharing, which originates in a Curry-Howard interpretation of a deep-inference system for intuitionistic logic. It has been shown that it allows fully lazy sharing to be reproduced in a typed setting. In this paper we prove strong normalization of the typed atomic Lambda-Calculus using Tait’s reducibility method.
C.-h. Luke Ong - One of the best experts on this subject based on the ideXlab platform.
-
The Safe Lambda Calculus
Logical Methods in Computer Science, 2009Co-Authors: William Blum, C.-h. Luke OngAbstract:Safety is a syntactic condition of higher-order grammars that constrains occurrences of variables in the production rules according to their type-theoretic order. In this paper, we introduce the safe Lambda Calculus, which is obtained by transposing (and generalizing) the safety condition to the setting of the simply-typed Lambda Calculus. In contrast to the original definition of safety, our Calculus does not constrain types (to be homogeneous). We show that in the safe Lambda Calculus, there is no need to rename bound variables when performing substitution, as variable capture is guaranteed not to happen. We also propose an adequate notion of beta-reduction that preserves safety. In the same vein as Schwichtenberg's 1976 characterization of the simply-typed Lambda Calculus, we show that the numeric functions representable in the safe Lambda Calculus are exactly the multivariate polynomials; thus conditional is not definable. We also give a characterization of representable word functions. We then study the complexity of deciding beta-eta equality of two safe simply-typed terms and show that this problem is PSPACE-hard. Finally we give a game-semantic analysis of safety: We show that safe terms are denoted by `P-incrementally justified strategies'. Consequently pointers in the game semantics of safe Lambda-terms are only necessary from order 4 onwards.
-
TLCA - The safe Lambda Calculus
Lecture Notes in Computer Science, 2007Co-Authors: William Blum, C.-h. Luke OngAbstract:Safety is a syntactic condition of higher-order grammars that constrains occurrences of variables in the production rules according to their type-theoretic order. In this paper, we introduce the safe Lambda Calculus, which is obtained by transposing (and generalizing) the safety condition to the setting of the simply-typed Lambda Calculus. In contrast to the original definition of safety, our Calculus does not constrain types (to be homogeneous). We show that in the safe Lambda Calculus, there is no need to rename bound variables when performing substitution, as variable capture is guaranteed not to happen.We also propose an adequate notion of β-reduction that preserves safety. In the same vein as Schwichtenberg's 1976 characterization of the simply-typed Lambda Calculus, we show that the numeric functions representable in the safe Lambda Calculus are exactly the multivariate polynomials; thus conditional is not definable. Finally we give a game-semantic analysis of safety: We show that safe terms are denoted by P-incrementally justified strategies. Consequently pointers in the game semantics of safe λ-terms are only necessary from order 4 onwards.
William Blum - One of the best experts on this subject based on the ideXlab platform.
-
Ong – The safe Lambda Calculus
Springer, 2015Co-Authors: William BlumAbstract:We consider a syntactic restriction for higher-order grammars called safety that constrains occurrences of variables in the production rules according to their type-theoretic order. We transpose and generalize this restriction to the setting of the simply-typed Lambda Calculus, giving rise to what we call the safe Lambda Calculus. We analyze its expressivity and obtain a result in the same vein as Schwichtenberg’s 1976 characterization of the simply-typed Lambda Calculus: the numeric functions representable in the safe Lambda Calculus are exactly the multivariate polynomi-als; thus conditional is not definable. We also give a similar characterization for representable word functions. We then examine the complexity of deciding beta-eta equality of two safe simply-typed terms and show that this problem is PSPACE-hard. The safety restriction is then extended to other applied Lambda calculi featuring re-cursion and references such as PCF and Idealized Algol (IA for short). The next contribution concerns game semantics. We introduce a new concrete pre-sentation of this semantics using the theory of traversals. It is shown that the reveale
-
The Safe Lambda Calculus
Logical Methods in Computer Science, 2009Co-Authors: William Blum, C.-h. Luke OngAbstract:Safety is a syntactic condition of higher-order grammars that constrains occurrences of variables in the production rules according to their type-theoretic order. In this paper, we introduce the safe Lambda Calculus, which is obtained by transposing (and generalizing) the safety condition to the setting of the simply-typed Lambda Calculus. In contrast to the original definition of safety, our Calculus does not constrain types (to be homogeneous). We show that in the safe Lambda Calculus, there is no need to rename bound variables when performing substitution, as variable capture is guaranteed not to happen. We also propose an adequate notion of beta-reduction that preserves safety. In the same vein as Schwichtenberg's 1976 characterization of the simply-typed Lambda Calculus, we show that the numeric functions representable in the safe Lambda Calculus are exactly the multivariate polynomials; thus conditional is not definable. We also give a characterization of representable word functions. We then study the complexity of deciding beta-eta equality of two safe simply-typed terms and show that this problem is PSPACE-hard. Finally we give a game-semantic analysis of safety: We show that safe terms are denoted by `P-incrementally justified strategies'. Consequently pointers in the game semantics of safe Lambda-terms are only necessary from order 4 onwards.
-
the safe Lambda Calculus
International Conference on Typed Lambda Calculi and Applications, 2007Co-Authors: William Blum, C Luke H OngAbstract:Safety is a syntactic condition of higher-order grammars that constrains occurrences of variables in the production rules according to their type-theoretic order. In this paper, we introduce the safe Lambda Calculus, which is obtained by transposing (and generalizing) the safety condition to the setting of the simply-typed Lambda Calculus. In contrast to the original definition of safety, our Calculus does not constrain types (to be homogeneous). We show that in the safe Lambda Calculus, there is no need to rename bound variables when performing substitution, as variable capture is guaranteed not to happen.We also propose an adequate notion of β-reduction that preserves safety. In the same vein as Schwichtenberg's 1976 characterization of the simply-typed Lambda Calculus, we show that the numeric functions representable in the safe Lambda Calculus are exactly the multivariate polynomials; thus conditional is not definable. Finally we give a game-semantic analysis of safety: We show that safe terms are denoted by P-incrementally justified strategies. Consequently pointers in the game semantics of safe λ-terms are only necessary from order 4 onwards.
-
TLCA - The safe Lambda Calculus
Lecture Notes in Computer Science, 2007Co-Authors: William Blum, C.-h. Luke OngAbstract:Safety is a syntactic condition of higher-order grammars that constrains occurrences of variables in the production rules according to their type-theoretic order. In this paper, we introduce the safe Lambda Calculus, which is obtained by transposing (and generalizing) the safety condition to the setting of the simply-typed Lambda Calculus. In contrast to the original definition of safety, our Calculus does not constrain types (to be homogeneous). We show that in the safe Lambda Calculus, there is no need to rename bound variables when performing substitution, as variable capture is guaranteed not to happen.We also propose an adequate notion of β-reduction that preserves safety. In the same vein as Schwichtenberg's 1976 characterization of the simply-typed Lambda Calculus, we show that the numeric functions representable in the safe Lambda Calculus are exactly the multivariate polynomials; thus conditional is not definable. Finally we give a game-semantic analysis of safety: We show that safe terms are denoted by P-incrementally justified strategies. Consequently pointers in the game semantics of safe λ-terms are only necessary from order 4 onwards.
Silvia Ghilezan - One of the best experts on this subject based on the ideXlab platform.
-
Kripke-style Semantics and Completeness for Full Simply Typed Lambda Calculus
Journal of Logic and Computation, 2020Co-Authors: Simona Kašterović, Silvia GhilezanAbstract:Abstract Full simply typed Lambda Calculus is the simply typed Lambda Calculus extended with product types and sum types. We propose a Kripke-style semantics for full simply typed Lambda Calculus. We then prove soundness and completeness of type assignment in full simply typed Lambda Calculus with respect to the proposed semantics. The key point in the proof of completeness is the notion of a canonical model.
-
ICTCS - Confluence of Untyped Lambda Calculus via Simple Types
Lecture Notes in Computer Science, 2001Co-Authors: Silvia Ghilezan, Viktor KuncakAbstract:We present a new proof of confluence of the untyped Lambda Calculus by reducing the confluence of s-reduction in the untyped Lambda Calculus to the confluence of s-reduction in the simply typed Lambda Calculus. This is achieved by embedding typed Lambda terms into simply typed Lambda terms. Using this embedding, an auxiliary reduction, and s-reduction on simply typed Lambda terms we define a new reduction on all Lambda terms. The transitive closure of the reduction defined is s-reduction on all Lambda terms. This embedding allows us to use the confluence of s-reduction on simply typed Lambda terms and thus prove the confluence of the reduction defined. As a consequence we obtain the confluence of s-reduction in the untyped Lambda Calculus.
