×

Boolean minors. (English) Zbl 0837.68081

Summary: We study the problem of characterizing monotonic Boolean functions and threshold Boolean functions by forbidden Boolean minors. Completely monotonic functions, \(k\)-monotonic functions and regular functions are characterized by forbidden minors. A bound on the number of minimal forbidden minors of \(k\)-comparable functions is obtained. We prove that there is a finite list of minimal forbidden minors for \(k\)-assumable functions and give a sharp bound on the dimension of minimal forbidden minors of \(k\)-assumable functions. We prove the conjecture that a Boolean function is \((m, 2^m)\)-assumable if and only if it has no parity function of dimension \(m + 1\) as minor for \(m = 1,2\).

MSC:

68R05 Combinatorics in computer science
94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
06E30 Boolean functions
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bertolazzi, P.; Sassano, A., An O(mn) algorithm for regular set-covering problem, Theoret. Comput. Sci., 54, 237-247 (1987) · Zbl 0632.68068
[2] Bertolazzi, P.; Sassano, A., A class of polynomially solvable set-covering problems, SIAM J. Discrete Math, 1, 306-316 (1988) · Zbl 0678.05048
[3] Boros, E.; Hammer, P. L.; Sun, X., Recognizing threshold Boolean functions without dualization, (Technical Report 91-21 (1991), RUTCOR, Rutgers University: RUTCOR, Rutgers University New Brunswick, NJ 08903)
[4] Chow, C. K., Boolean functions realizable with single threshold devices, (Proc. Inst. Radio Engineers, 49 (1961)), 370-371
[5] Chvátal, V.; Hammer, P. L., Aggregation of inequalities in integer programming, Ann. Discrete Math., 1, 145-162 (1977)
[6] Crama, Y., Dualization of regular Boolean functions, Discrete Appl. Math., 16, 79-85 (1987) · Zbl 0605.94011
[7] Elgot, C. C., Truth functions realizable by single threshold organs (1961)
[8] Gabelman, I. J., The functional behavior of majority (threshold) elements, (Ph.D. Thesis (1961), Department of Electrical Engineering, Syracuse University: Department of Electrical Engineering, Syracuse University Syracuse, New York) · Zbl 0118.33103
[9] Garey, M. R.; Johnson, D. S., Computers and Intractability, (A Guide to the Theory of Np-Completeness (1979), W.H. Freeman: W.H. Freeman San Francisco) · Zbl 0369.90053
[10] Hammer, P. L.; Johnson, E. L.; Peled, U. N., Regular 0-1 programs, Cahiers Centre Etudes Rech. Opér., 16, 267-276 (1974) · Zbl 0304.90081
[11] Hammer, P. L.; Peled, U. N.; Pollatschek, M. A., An algorithm to dualize a regular switching function, IEEE Trans. Comput. C-28, 238-243 (1979) · Zbl 0394.94036
[12] Hu, T. C., Threshold Logic (1965), University of California Press: University of California Press Berkeley · Zbl 0166.27101
[13] Mahadev, V. R.; Peled, U. N., On a conjecture of Wang and Williams, J. Graph Theory, 15, 115-120 (1991) · Zbl 0732.05051
[14] Muroga, S., Threshold Logic and Its Applications (1971), Wiley-Interscience: Wiley-Interscience New York · Zbl 0243.94014
[15] Muroga, S.; Toda, I.; Takasu, S., Theory of majority decision elements, J. Franklin Inst., 271, 376-418 (1961) · Zbl 0196.51705
[16] Paull, M. C.; McCluskey, E. J., Boolean functions realizable with single threshold devices, (Proc. IRE, 48 (1960)), 1335-1337
[17] Peled, U.; Simeone, B., Polynomial-time algorithms for regular set-covering and threshold synthesis, Discrete Appl. Math., 12, 57-69 (1985) · Zbl 0619.05020
[18] Wang, C., Competition graphs, threshold graphs and threshold Boolean functions, (Ph.D Thesis (1991), Rutgers University)
[19] Wang, C., On strongly heavy graphs (1993), manuscript · Zbl 0801.05059
[20] Wang, C.; Williams, A. C., The threshold order of a Boolean function, Discrete Appl. Math., 31, 51-69 (1991) · Zbl 0728.94015
[21] Wang, C.; Williams, A. C., The threshold weight of a graph, J. Graph Theory, 15, 235-249 (1991) · Zbl 0741.05073
[22] Winder, R. O., Single state threshold logic, (IEEE Symp. on Switching Circuit Theory and Logical Design (1961)), 321-332 · Zbl 0207.02101
[23] Winder, R. O., Threshold logic, (Ph.D Thesis (1962), Princeton University) · Zbl 0207.02101
[24] Yajima, S.; Ibaraki, T., A theory of completely monotonic functions and its applications to threshold logic, IEEE TC C-17, 3, 214-229 (1968) · Zbl 0172.30301
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.