A complete classification of equational classes of threshold functions included in clones

DOI10.1051/RO/2014034MaRDI QIDQ5247685zbMATH OpenOpenAlexFDO

Authors Miguel Couceiro, Erkko Lehtonen, Karsten Schölzel

Publication date 27 April 2015

Published in RAIRO - Operations Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1310.7041

zbMATH Keywords

Boolean functionsclonesequational classesrelational constraintsthreshold functions

Mathematics Subject Classification ID

Boolean functions (06E30) Operations and polynomials in algebraic structures, primal algebras (08A40)

Abstract: The class of threshold functions is known to be characterizable by functional equations or, equivalently, by pairs of relations, which are called relational constraints. It was shown by Hellerstein that this class cannot be characterized by a finite number of such objects. In this paper, we investigate classes of threshold functions which arise as intersections of the class of all threshold functions with clones of Boolean functions, and provide a complete classification of such intersections in respect to whether they have finite characterizations. Moreover, we provide a characterizing set of relational constraints for each class of threshold functions arising in this way.

Recommendations

• Equationally closed classes of partial Boolean functions
• On equational definability of function classes
• The class of balanced algebraic threshold functions
• scientific article; zbMATH DE number 3991417
• Construction of universal enumerators and formulas for threshold functions
• Closed classes of functions, generalized constraints, and clusters
• On the structure of equationally closed classes
• On the constructive characterization of threshold functions
• On the lattice of equational classes of Boolean functions and its closed intervals
• On the classes of Boolean functions generated by maximal partial ultraclones

Cites work

• A CLASS OF MAJORITY GAMES
• A theory of coalition formation in committees
• Closed systems of functions and predicates
• Coalition formation in simple games with dominant players
• Composition of Post classes and normal forms of Boolean functions
• Discrete integrals based on comonotonic modularity
• Equational characterizations of Boolean function classes
• Extensions of functions of 0-1 variables and applications to combinatorial optimization
• Function Algebras on Finite Sets
• Galois theory for minors of finite functions
• Generalizations of Świerczkowski's lemma and the arity gap of finite functions
• scientific article; zbMATH DE number 2118880 (Why is no real title available?)
• scientific article; zbMATH DE number 3385535 (Why is no real title available?)
• Minimizing a Submodular Function on a Lattice
• On a quasi-ordering on Boolean functions
• On closed sets of relational constraints and classes of functions closed under variable substitutions
• On defining sets of vertices of the hypercube by linear inequalities
• On Galois Connections between External Operations and Relational Constraints: Arity Restrictions and Operator Decompositions
• On generalized constraints and certificates
• On the effect of variable identification on the essential arity of functions on finite sets
• Post classes characterized by functional terms
• Simple games and magic squares
• The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)

Cited in

(3)

• Content and singletons bring unique identification minors
• An infinite descending chain of Boolean subfunctions consisting of threshold functions
• Reconstructing permutations from identification minors

This page was built for publication: A complete classification of equational classes of threshold functions included in clones

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5247685)