×

A complete classification of equational classes of threshold functions included in clones. (English) Zbl 1330.06009

Threshold functions are Boolean functions whose true points can be separated from the false points by a hyperplane when considered as elements of the \(n\)-dimensional real space. These functions are characterizable by functional equations or, equivalently, by relational constraints, but the thresholdness property cannot be captured by a finite set of relational constraints.
The aim of the present paper is to determine, for each clone of Boolean functions, whether its intersection with the class of threshold functions is finitely characterizable by relational constraints. The main results are the following: the classification of all intersections of clones with the class of all threshold functions, giving the corresponding characterizing set of relational constraints, showing the connection between the classes of functions characterizable by the relational constraints.

MSC:

06E30 Boolean functions
08A40 Operations and polynomials in algebraic structures, primal algebras
94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] J.C. Bioch and TIbaraki, Generating and approximating nondominated coteries. IEEE Trans. Parallel Distrib. Syst.6 (1995) 905-914. · Zbl 05107672 · doi:10.1109/71.466629
[2] 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: Cybernetics5, 243-252, 531-539 (1969)
[3] C.K. Chow, Boolean functions realizable with single threshold devices. Proc. Inst. Radio Engineers49 (1961) 370-371.
[4] M. Couceiro, On Galois connections between external functions and relational constraints: arity restrictions and operator decompositions, Acta Sci. Math. (Szeged)72 (2006) 15-35. · Zbl 1111.08001
[5] M. Couceiro and S. Foldes, On closed sets of relational constraints and classes of functions closed under variable substitution, Algebra Universalis54 (2005) 149-165. · Zbl 1095.08002 · doi:10.1007/s00012-005-1933-1
[6] 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. · Zbl 1202.08001 · doi:10.1142/S012905410700508X
[7] M. Couceiro and E. Lehtonen, Generalizations of Świerczkowski’s lemma and the arity gap of finite functions, Discrete Math.309 (2009) 5905-5912. · Zbl 1200.08001 · doi:10.1016/j.disc.2009.04.009
[8] M. Couceiro and J.-L. Marichal, Discrete integrals based on comonotonic modularity, Axioms2 (2013) 390-403. · Zbl 1296.28021 · doi:10.3390/axioms2030390
[9] M. Couceiro and M. Pouzet, On a quasi-ordering on Boolean functions. Theoret. Comput. Sci.396 (2008) 71-87. · Zbl 1143.06005 · doi:10.1016/j.tcs.2008.01.025
[10] M. Couceiro, S. Foldes and E. Lehtonen, Composition of Post classes and normal forms of Boolean functions, Discrete Math.306 (2006) 3223-3243. · Zbl 1110.06017 · doi:10.1016/j.disc.2006.06.014
[11] K. Denecke, M. Erné and S.L. Wismath, Galois Connections and Applications, Kluwer Academic Publishers, Dordrecht (2004) · Zbl 1050.06001
[12] O. Ekin, S. Foldes, P.L. Hammer and L. Hellerstein, Equational characterizations of Boolean function classes. Discrete Math.211 (2000) 27-51. · Zbl 0947.06008 · doi:10.1016/S0012-365X(99)00132-6
[13] 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.
[14] S. Foldes and G.R. Pogosyan, Post classes characterized by functional terms. Discrete Appl. Math.142 (2004) 35-51. · Zbl 1051.06011 · doi:10.1016/j.dam.2003.01.002
[15] D. Geiger, Closed systems of functions and predicates, Pacific J. Math.27 (1968) 95-100. · Zbl 0186.02502 · doi:10.2140/pjm.1968.27.95
[16] L. Hellerstein, On generalized constraints and certificates, Discrete Math.226 (2001) 211-232. · Zbl 0965.06016 · doi:10.1016/S0012-365X(00)00166-7
[17] J.R. Isbell, A class of majority games, Q. J. Math.7 (1956) 183-187. · Zbl 0073.13401 · doi:10.1093/qmath/7.1.183
[18] S.W. Jablonski, G.P. Gawrilow and W.B. Kudrjawzew, Boolesche Funktionen und Postsche Klassen, Vieweg, Braunschweig (1970).
[19] R.G. Jeroslow, On defining sets of vertices of the hypercube by linear inequalities, Discrete Math.11 (1975) 119-124. · Zbl 0297.52009 · doi:10.1016/0012-365X(75)90003-5
[20] D. Lau, Function Algebras on Finite Sets. Springer-Verlag, Berlin, Heidelberg (2006) · Zbl 1105.08001
[21] S.R. Lay, Convex sets and their applications, Dover (2007).
[22] L. Lovász, Submodular functions and convexity, Mathematical programming, in proc. 11th int. Symp., Bonn (1982) 235-257.
[23] S. Muroga, Threshold logic and its applications, Wiley-Interscience, New York (1971) · Zbl 0243.94014
[24] B. Peleg, A theory of coalition formation in committees, J. Math. Econom.7 115-134 (1980) · Zbl 0434.90009 · doi:10.1016/0304-4068(80)90001-4
[25] B. Peleg, Coalition formation in simple games with dominant players, Int. J. Game Theory10 (1981) 11-33. · Zbl 0454.90097 · doi:10.1007/BF01770068
[26] N. Pippenger, Galois theory for minors of finite functions. Discrete Math.254 (2002) 405-419. · Zbl 1010.06012 · doi:10.1016/S0012-365X(01)00297-7
[27] 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.
[28] E. Post, The Two-Valued Iterative Systems of Mathematical Logic, Annals of Mathematical Studies, Vol. 5, Princeton University Press, Princeton, NJ (1941) · Zbl 0063.06326
[29] I. Singer, Extensions of functions of 0-1 variables and applications to combinatorial optimization. Numer. Funct. Anal. Optim.7 (1984) 23-62. · Zbl 0546.90066 · doi:10.1080/01630568508816180
[30] A. Taylor and W. Zwicker, Simple games and magic squares. J. Combin. Theory Ser. A71 (1995) 67-88. · Zbl 0837.05026 · doi:10.1016/0097-3165(95)90016-0
[31] D.M. Topkis, Minimizing a submodular function on a lattice. Oper. Res.26 (1978) 305-321. · Zbl 0379.90089 · doi:10.1287/opre.26.2.305
[32] R.O. Winder, Threshold Logic, Ph.D. thesis, Mathematics Department, Princeton University (1962).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.