Geodesic
A complete classification of equational classes of threshold functions included in clones
Couceiro, Miguel1  ; Lehtonen, Erkko2, 3 ; Schölzel, Karsten4
1 LAMSADE – CNRS, Université Paris-Dauphine, Place du Maréchal de Lattre de Tassigny, 75775 Paris Cedex 16, France.
2 Computer Science and Communications Research Unit, University of Luxembourg, 1359 Luxembourg, Luxembourg.
3 Centro de Álgebra da Universidade de Lisboa, Avenida Professor Gama Pinto 2, 1649-003 Lisboa, Portugal.
4 Mathematics Research Unit, University of Luxembourg, 1359 Luxembourg, Luxembourg.
RAIRO - Operations Research - Recherche Opérationnelle, Special ROADEF 2013, Tome 49 (2015) no. 1, pp. 39-66

Voir la notice de l'article provenant de la source Numdam

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.

Reçu le :
Accepté le :
DOI : 10.1051/ro/2014034
Classification : 06E30, 91A99
Keywords: Boolean functions, threshold functions, constraints, clones, equational classes

Couceiro, Miguel 1 ; Lehtonen, Erkko 2, 3 ; Schölzel, Karsten 4

1 LAMSADE – CNRS, Université Paris-Dauphine, Place du Maréchal de Lattre de Tassigny, 75775 Paris Cedex 16, France.
2 Computer Science and Communications Research Unit, University of Luxembourg, 1359 Luxembourg, Luxembourg.
3 Centro de Álgebra da Universidade de Lisboa, Avenida Professor Gama Pinto 2, 1649-003 Lisboa, Portugal.
4 Mathematics Research Unit, University of Luxembourg, 1359 Luxembourg, Luxembourg. 
@article{RO_2015__49_1_39_0,
     author = {Couceiro, Miguel and Lehtonen, Erkko and Sch\"olzel, Karsten},
     title = {A complete classification of equational classes of threshold functions included in clones},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {39--66},
     publisher = {EDP-Sciences},
     volume = {49},
     number = {1},
     year = {2015},
     doi = {10.1051/ro/2014034},
     mrnumber = {3349115},
     zbl = {1330.06009},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1051/ro/2014034/}
}
TY  - JOUR
AU  - Couceiro, Miguel
AU  - Lehtonen, Erkko
AU  - Schölzel, Karsten
TI  - A complete classification of equational classes of threshold functions included in clones
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2015
SP  - 39
EP  - 66
VL  - 49
IS  - 1
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/articles/10.1051/ro/2014034/
DO  - 10.1051/ro/2014034
LA  - en
ID  - RO_2015__49_1_39_0
ER  - 
%0 Journal Article
%A Couceiro, Miguel
%A Lehtonen, Erkko
%A Schölzel, Karsten
%T A complete classification of equational classes of threshold functions included in clones
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2015
%P 39-66
%V 49
%N 1
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/articles/10.1051/ro/2014034/
%R 10.1051/ro/2014034
%G en
%F RO_2015__49_1_39_0
Couceiro, Miguel; Lehtonen, Erkko; Schölzel, Karsten. A complete classification of equational classes of threshold functions included in clones. RAIRO - Operations Research - Recherche Opérationnelle, Special ROADEF 2013, Tome 49 (2015) no. 1, pp. 39-66. doi: 10.1051/ro/2014034

Cité par Sources :