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.

Accepted:

DOI: 10.1051/ro/2014034

Keywords: Boolean functions, threshold functions, constraints, clones, equational classes

^{1}; Lehtonen, Erkko

^{2, 3}; Schölzel, Karsten

^{4}

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

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

and ,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

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

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

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

and ,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

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

and ,Discrete integrals based on comonotonic modularity, Axioms 2 (2013) 390–403. | DOI | Zbl

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

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

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

Equational characterizations of Boolean function classes. Discrete Math. 211 (2000) 27–51. | DOI | MR | Zbl

, , and ,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.

Post classes characterized by functional terms. Discrete Appl. Math. 142 (2004) 35–51. | DOI | MR | Zbl

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

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

,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

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

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

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

,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

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

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

and ,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

*Cited by Sources: *