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

Couceiro, Miguel; Lehtonen, Erkko; Schölzel, Karsten

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

Type

Article accepté pour publication ou publié

Lien vers un document non conservé dans cette base

https://hal.archives-ouvertes.fr/hal-01090621

Date

2015

Nom de la revue

RAIRO - Operations Research

Volume

Numéro

Pages

39-66

Identifiant publication

10.1051/ro/2014034

Métadonnées

Afficher la notice complète

Auteur(s)

Couceiro, Miguel
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Lehtonen, Erkko

University of Luxembourg, Computer Science Department
Schölzel, Karsten
Mathematics Research Unit

Résumé (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.

Mots-clés

Boolean functions; threshold functions; constraints; clones; equational classes