A complete classification of equational classes of threshold functions included in clones
Couceiro, Miguel; Lehtonen, Erkko; Schölzel, Karsten (2015), A complete classification of equational classes of threshold functions included in clones, RAIRO - Operations Research, 49, 1, p. 39-66. 10.1051/ro/2014034
TypeArticle accepté pour publication ou publié
External document linkhttps://hal.archives-ouvertes.fr/hal-01090621
Journal nameRAIRO - Operations Research
MetadataShow full item record
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
University of Luxembourg, Computer Science Department
Mathematics Research Unit
Abstract (EN)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.
Subjects / KeywordsBoolean functions; threshold functions; constraints; clones; equational classes
Showing items related by title and author.
A Solution to a Problem of D. Lau: Complete Classification of Intervals in the Lattice of Partial Boolean Clones Couceiro, Miguel; Haddad, Lucien; Schölzel, Karsten; Waldhauser, Tamás (2013) Communication / Conférence
A Solution to a Problem of D. Lau: Complete Classification of Intervals in the Lattice of Partial Boolean Clones Couceiro, Miguel; Haddad, Lucien; Schölzel, Karsten; Waldhauser, Tamás (2017) Article accepté pour publication ou publié