Volume 49, Number 1, January-March 2015Special ROADEF 2013
|Page(s)||39 - 66|
|Published online||17 December 2014|
A complete classification of equational classes of threshold functions included in clones
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.
Received: 6 September 2013
Accepted: 27 May 2014
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.
Mathematics Subject Classification: 06E30 / 91A99
Key words: Boolean functions / threshold functions / constraints / clones / equational classes
© EDP Sciences, ROADEF, SMAI, 2014
Initial download of the metrics may take a while.