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

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

doi:10.1051/ro/2014034

Couceiro, Miguel ¹ ; Lehtonen, Erkko ^2,³ ; Schölzel, Karsten ⁴

¹ LAMSADE – CNRS, Université Paris-Dauphine, Place du Maréchal de Lattre de Tassigny, 75775 Paris Cedex 16, France.
² Computer Science and Communications Research Unit, University of Luxembourg, 1359 Luxembourg, Luxembourg.
³ Centro de Álgebra da Universidade de Lisboa, Avenida Professor Gama Pinto 2, 1649-003 Lisboa, Portugal.
⁴ Mathematics Research Unit, University of Luxembourg, 1359 Luxembourg, Luxembourg.

RAIRO - Operations Research - Recherche Opérationnelle, Tome 49 (2015) no. 1, pp. 39-66.

Résumé

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 : 2013-09-06
Accepté le : 2014-05-27

MR Zbl

DOI : 10.1051/ro/2014034

Classification : 06E30, 91A99
Mots clés : Boolean functions, threshold functions, constraints, clones, equational classes

Affiliations des auteurs :

Couceiro, Miguel ¹ ; Lehtonen, Erkko ^{2, 3} ; Schölzel, Karsten ⁴

@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://www.numdam.org/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://www.numdam.org/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://www.numdam.org/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, Tome 49 (2015) no. 1, pp. 39-66. doi : 10.1051/ro/2014034. http://www.numdam.org/articles/10.1051/ro/2014034/

Bibliographie
Cité par

J.C. Bioch and Tibaraki, Generating and approximating nondominated coteries. IEEE Trans. Parallel Distrib. Syst. 6 (1995) 905–914. | DOI

V.G. Bodnarčuk, L.A. Kalužnin, V.N. Kotov and B.A. Romov, Galois theory for Post algebras, I, II, Kibernetika 3, 1–10, 5, 1–9 (1969) (Russian). English translation: Cybernetics 5, 243–252, 531–539 (1969) | MR | Zbl

C.K. Chow, Boolean functions realizable with single threshold devices. Proc. Inst. Radio Engineers 49 (1961) 370–371. | MR

M. Couceiro, On Galois connections between external functions and relational constraints: arity restrictions and operator decompositions, Acta Sci. Math. (Szeged) 72 (2006) 15–35. | MR | Zbl

M. Couceiro and S. Foldes, On closed sets of relational constraints and classes of functions closed under variable substitution, Algebra Universalis 54 (2005) 149–165. | DOI | MR | Zbl

M. Couceiro and E. Lehtonen, On the effect of variable identification on the essential arity of functions on finite sets. Int. J. Found. Comput. Sci. 18 (2007) 975–986. | DOI | MR | Zbl

M. Couceiro and E. Lehtonen, Generalizations of Świerczkowski’s lemma and the arity gap of finite functions, Discrete Math. 309 (2009) 5905–5912. | DOI | MR | Zbl

M. Couceiro and J.-L. Marichal, Discrete integrals based on comonotonic modularity, Axioms 2 (2013) 390–403. | DOI | Zbl

M. Couceiro and M. Pouzet, On a quasi-ordering on Boolean functions. Theoret. Comput. Sci. 396 (2008) 71–87. | DOI | MR | Zbl

M. Couceiro, S. Foldes and E. Lehtonen, Composition of Post classes and normal forms of Boolean functions, Discrete Math. 306 (2006) 3223–3243. | DOI | MR | Zbl

K. Denecke, M. Erné and S.L. Wismath, Galois Connections and Applications, Kluwer Academic Publishers, Dordrecht (2004) | Zbl

O. Ekin, S. Foldes, P.L. Hammer and L. Hellerstein, Equational characterizations of Boolean function classes. Discrete Math. 211 (2000) 27–51. | DOI | MR | Zbl

C.C. Elgot, Truth functions realizable by single threshold organs, AIEE Conf. Paper 60-1311, Oct. 1960, revised Nov. 1960; also IEEE Symposium on Swithing Circuit Theory and Logical Design (1961) 225–245.

S. Foldes and G.R. Pogosyan, Post classes characterized by functional terms. Discrete Appl. Math. 142 (2004) 35–51. | DOI | MR | Zbl

D. Geiger, Closed systems of functions and predicates, Pacific J. Math. 27 (1968) 95–100. | DOI | MR | Zbl

L. Hellerstein, On generalized constraints and certificates, Discrete Math. 226 (2001) 211–232. | DOI | MR | Zbl

J.R. Isbell, A class of majority games, Q. J. Math. 7 (1956) 183–187. | DOI | MR | Zbl

S.W. Jablonski, G.P. Gawrilow and W.B. Kudrjawzew, Boolesche Funktionen und Postsche Klassen, Vieweg, Braunschweig (1970). | MR | Zbl

R.G. Jeroslow, On defining sets of vertices of the hypercube by linear inequalities, Discrete Math. 11 (1975) 119–124. | DOI | MR | Zbl

D. Lau, Function Algebras on Finite Sets. Springer-Verlag, Berlin, Heidelberg (2006) | Zbl

S.R. Lay, Convex sets and their applications, Dover (2007).

L. Lovász, Submodular functions and convexity, Mathematical programming, in proc. 11th int. Symp., Bonn (1982) 235–257. | MR | Zbl

S. Muroga, Threshold logic and its applications, Wiley-Interscience, New York (1971) | MR

B. Peleg, A theory of coalition formation in committees, J. Math. Econom. 7 115–134 (1980) | DOI | MR | Zbl

B. Peleg, Coalition formation in simple games with dominant players, Int. J. Game Theory 10 (1981) 11–33. | DOI | MR | Zbl

N. Pippenger, Galois theory for minors of finite functions. Discrete Math. 254 (2002) 405–419. | DOI | MR | Zbl

R. Pöschel, Concrete representation of algebraic structures and a general Galois theory, in Contributions to General Algebra (Proc. Klagenfurt Conf., 1978), edited by H. Kautschitsch, W.B. Müller and W. Nöbauer, Verlag Johannes Heyn, Klagenfurt (1979) 249–272. | MR | Zbl

E. Post, The Two-Valued Iterative Systems of Mathematical Logic, Annals of Mathematical Studies, Vol. 5, Princeton University Press, Princeton, NJ (1941) | MR | Zbl

I. Singer, Extensions of functions of 0-1 variables and applications to combinatorial optimization. Numer. Funct. Anal. Optim. 7 (1984) 23–62. | DOI | MR | Zbl

A. Taylor and W. Zwicker, Simple games and magic squares. J. Combin. Theory Ser. A 71 (1995) 67–88. | DOI | MR | Zbl

D.M. Topkis, Minimizing a submodular function on a lattice. Oper. Res. 26 (1978) 305–321. | DOI | MR | Zbl

R.O. Winder, Threshold Logic, Ph.D. thesis, Mathematics Department, Princeton University (1962). | MR

Cité par Sources :