The Experts below are selected from a list of 23205 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.
-
from lambda calculus to Universal Algebra and back
Mathematical Foundations of Computer Science, 2008Co-Authors: Giulio Manzonetto, Antonino SalibraAbstract:We generalize to Universal Algebra concepts originating from lambda calculus and programming in order first to prove a new result on the lattice of λ-theories, and second a general theorem of pure Universal Algebra which can be seen as a meta version of the Stone Representation Theorem. The interest of a systematic study of the lattice λT of λ-theories grows out of several open problems on lambda calculus. For example, the failure of certain lattice identities in λT would imply that the problem of the orderincompleteness of lambda calculus raised by Selinger has a negative answer. In this paper we introduce the class of Church Algebras (which includes all Boolean Algebras, combinatory Algebras, rings with unit and the term Algebras of all λ-theories) to model the if-then-else instruction of programming and to extend some properties of Boolean Algebras to general Universal Algebras. The interest of Church Algebras is that each has a Boolean Algebra of central elements, which play the role of the idempotent elements in rings. Central elements are the key tool to represent any Church Algebra as a weak Boolean product of directly indecomposable Church Algebras and to prove the meta representation theorem mentioned above. We generalize the notion of easy λ-term and prove that any Church Algebra with an “easy set” of cardinality n admits (at the top) a lattice interval of congruences isomorphic to the free Boolean Algebra with n generators. This theorem has the following consequence for λT : for every recursively enumerable λtheory φ and each n, there is a λ-theory φn ≥ φ such that {ψ : ψ ≥ φn} “is” the Boolean lattice with 2 elements.
-
From λ-Calculus to Universal Algebra and Back
Lecture Notes in Computer Science, 1Co-Authors: Giulio Manzonetto, Antonino SalibraAbstract:We generalize to Universal Algebra concepts originating fromλ-calculus and programming to prove a new result onthe lattice λTof λ-theories, and ageneral theorem of pure Universal Algebra which can be seen as ameta version of the Stone Representation Theorem. In this paper weintroduce the class of Church Algebras(which includes allBoolean Algebras, combinatory Algebras, rings with unit and theterm Algebras of all λ-theories) to model the"if-then-else" instruction of programming. The interest of ChurchAlgebras is that each has a Boolean Algebra of central elements,which play the role of the idempotent elements in rings. Centralelements are the key tool to represent any Church Algebra as a weakBoolean product of indecomposable Church Algebras and to prove themeta representation theorem mentioned above. We generalize thenotion of easy λ-term of lambda calculus to provethat any Church Algebra with an "easy set" of cardinalitynadmits (at the top) a lattice interval of congruencesisomorphic to the free Boolean Algebra with ngenerators.This theorem has the following consequence for the lattice ofλ-theories: for every recursively enumerableλ-theory φand each n, thereis a λ-theory φn? φsuch that {ψ: ψ? φn} "is" the Booleanlattice with 2 nelements.
Marcel Tonga - One of the best experts on this subject based on the ideXlab platform.
-
On the lattice and the Algebra of fuzzy subsets of a Universal Algebra
Fuzzy Sets and Systems, 2020Co-Authors: Armand Fotso Tatuene, Marcel TongaAbstract:Abstract For a given Universal Algebra, the set of all its fuzzy subsets is endowed with two structures: a structure of Algebra called the fuzzy Algebra (or the Algebra of fuzzy subsets) and a structure of bounded lattice called the lattice of fuzzy subsets. In this paper, first of all, we construct some subuniverses of this fuzzy Algebra and give a way to generate such subuniverses. We characterize the subuniverse generated by a fuzzy point of this fuzzy Algebra. Some subAlgebras containing the subAlgebra generated by a finite set of fuzzy points of the fuzzy Algebra are specified. We also describe some subuniverses of the initial Universal Algebra induced by those of its fuzzy Algebra, and vice versa. We then give some properties of fuzzy subAlgebras of this Universal Algebra, describe some fuzzy subAlgebras generated by others fuzzy subAlgebras, and give a partial characterization of Universal Algebras in which the set of all fuzzy subAlgebras is a subuniverse of their fuzzy Algebras. After that, we characterize some properties which can be transfered between the codomain lattice of fuzzy subsets (the lattice of truth values) and the lattice of fuzzy subsets. Later, we show that there exists some subsets of the set of all fuzzy subsets which can be both subuniverses of the fuzzy Algebra and sublattices of the lattice of fuzzy subsets: that means, these subsets are endowed with a double structure like the set of all fuzzy subsets of the given Universal Algebra; and finally, we introduce the residuation of some of them by defining the residual operations in a certain way.
Giulio Manzonetto - 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.
-
from lambda calculus to Universal Algebra and back
Mathematical Foundations of Computer Science, 2008Co-Authors: Giulio Manzonetto, Antonino SalibraAbstract:We generalize to Universal Algebra concepts originating from lambda calculus and programming in order first to prove a new result on the lattice of λ-theories, and second a general theorem of pure Universal Algebra which can be seen as a meta version of the Stone Representation Theorem. The interest of a systematic study of the lattice λT of λ-theories grows out of several open problems on lambda calculus. For example, the failure of certain lattice identities in λT would imply that the problem of the orderincompleteness of lambda calculus raised by Selinger has a negative answer. In this paper we introduce the class of Church Algebras (which includes all Boolean Algebras, combinatory Algebras, rings with unit and the term Algebras of all λ-theories) to model the if-then-else instruction of programming and to extend some properties of Boolean Algebras to general Universal Algebras. The interest of Church Algebras is that each has a Boolean Algebra of central elements, which play the role of the idempotent elements in rings. Central elements are the key tool to represent any Church Algebra as a weak Boolean product of directly indecomposable Church Algebras and to prove the meta representation theorem mentioned above. We generalize the notion of easy λ-term and prove that any Church Algebra with an “easy set” of cardinality n admits (at the top) a lattice interval of congruences isomorphic to the free Boolean Algebra with n generators. This theorem has the following consequence for λT : for every recursively enumerable λtheory φ and each n, there is a λ-theory φn ≥ φ such that {ψ : ψ ≥ φn} “is” the Boolean lattice with 2 elements.
-
From λ-Calculus to Universal Algebra and Back
Lecture Notes in Computer Science, 1Co-Authors: Giulio Manzonetto, Antonino SalibraAbstract:We generalize to Universal Algebra concepts originating fromλ-calculus and programming to prove a new result onthe lattice λTof λ-theories, and ageneral theorem of pure Universal Algebra which can be seen as ameta version of the Stone Representation Theorem. In this paper weintroduce the class of Church Algebras(which includes allBoolean Algebras, combinatory Algebras, rings with unit and theterm Algebras of all λ-theories) to model the"if-then-else" instruction of programming. The interest of ChurchAlgebras is that each has a Boolean Algebra of central elements,which play the role of the idempotent elements in rings. Centralelements are the key tool to represent any Church Algebra as a weakBoolean product of indecomposable Church Algebras and to prove themeta representation theorem mentioned above. We generalize thenotion of easy λ-term of lambda calculus to provethat any Church Algebra with an "easy set" of cardinalitynadmits (at the top) a lattice interval of congruencesisomorphic to the free Boolean Algebra with ngenerators.This theorem has the following consequence for the lattice ofλ-theories: for every recursively enumerableλ-theory φand each n, thereis a λ-theory φn? φsuch that {ψ: ψ? φn} "is" the Booleanlattice with 2 nelements.
Karl Meinke - One of the best experts on this subject based on the ideXlab platform.
-
Topological methods for Algebraic specification
Theoretical Computer Science, 1996Co-Authors: Karl MeinkeAbstract:AbstractWe introduce an Algebraic construction for the Hausdorff extension H(A) of a many-sorted Universal Algebra A with respect to a family T of Hausdorff topologies on the carrier sets of A. This construction can be combined with other Algebraic constructions, such as the initial model construction, to provide methods for the Algebraic specification of uncountable Algebras, e.g. Algebras of reals, function spaces and streams
-
Universal Algebra in higher types
Theoretical Computer Science, 1992Co-Authors: Karl MeinkeAbstract:Abstract We develop the elementary theory of higher-order Universal Algebra using the nonstandard approach to finite type theory introduced by Henkin. Basic results include: existence theorems for free and initial higher type Algebras, a complete higher type equational calculus, and characterisation theorems for higher type equational and Horn classes.
-
ADT - Universal Algebra in Higher Types
Recent Trends in Data Type Specification, 1991Co-Authors: Karl MeinkeAbstract:We develop the elementary theory of higher-order Universal Algebra using the non-standard approach to finite type theory introduced by Henkin. Basic results include: existence theorems for free and initial higher type Algebras, a complete higher type equational calculus, and characterisation theorems for higher type equational and Horn classes.
Magnus Wahlstrom - One of the best experts on this subject based on the ideXlab platform.
-
kernelization of constraint satisfaction problems a study through Universal Algebra
Principles and Practice of Constraint Programming, 2017Co-Authors: Victor Lagerkvist, Magnus WahlstromAbstract:A kernelization algorithm for a computational problem is a procedure which compresses an instance into an equivalent instance whose size is bounded with respect to a complexity parameter. For the constraint satisfaction problem (CSP), there exist many results concerning upper and lower bounds for kernelizability of specific problems, but it is safe to say that we lack general methods to determine whether a given problem admits a kernel of a particular size. In this paper, we take an Algebraic approach to the problem of characterizing the kernelization limits of NP-hard CSP problems, parameterized by the number of variables. Our main focus is on problems admitting linear kernels, as has, somewhat surprisingly, previously been shown to exist. We show that a finite-domain CSP problem has a kernel with O(n) constraints if it can be embedded (via a domain extension) into a CSP which is preserved by a Maltsev operation. This result utilise a variant of the simple algorithm for Maltsev constraints. In the complementary direction, we give indication that the Maltsev condition might be a complete characterization for Boolean CSPs with linear kernels, by showing that an Algebraic condition that is shared by all problems with a Maltsev embedding is also necessary for the existence of a linear kernel unless NP \(\subseteq \) co-NP/poly.
-
kernelization of constraint satisfaction problems a study through Universal Algebra
arXiv: Computational Complexity, 2017Co-Authors: Victor Lagerkvist, Magnus WahlstromAbstract:A kernelization algorithm for a computational problem is a procedure which compresses an instance into an equivalent instance whose size is bounded with respect to a complexity parameter. For the Boolean satisfiability problem (SAT), and the constraint satisfaction problem (CSP), there exist many results concerning upper and lower bounds for kernelizability of specific problems, but it is safe to say that we lack general methods to determine whether a given SAT problem admits a kernel of a particular size. This could be contrasted to the currently flourishing research program of determining the classical complexity of finite-domain CSP problems, where almost all non-trivial tractable classes have been identified with the help of Algebraic properties. In this paper, we take an Algebraic approach to the problem of characterizing the kernelization limits of NP-hard SAT and CSP problems, parameterized by the number of variables. Our main focus is on problems admitting linear kernels, as has, somewhat surprisingly, previously been shown to exist. We show that a CSP problem has a kernel with O(n) constraints if it can be embedded (via a domain extension) into a CSP problem which is preserved by a Maltsev operation. We also study extensions of this towards SAT and CSP problems with kernels with O(n^c) constraints, c>1, based on embeddings into CSP problems preserved by a k-edge operation, k > c. These results follow via a variant of the celebrated few subpowers algorithm. In the complementary direction, we give indication that the Maltsev condition might be a complete characterization of SAT problems with linear kernels, by showing that an Algebraic condition that is shared by all problems with a Maltsev embedding is also necessary for the existence of a linear kernel unless NP is included in co-NP/poly.
