[en] Orthogonal forms of positive Boolean functions play an important role in reliability theory, since the probability that they take value 1 can be easily computed. However, few classes of disjunctive normal forms are known for which orthogonalization can be efficiently performed. An interesting class with this property is the class of shellable disjunctive normal forms (DNFs). In this paper, we present some new results about shellability. We establish that every positive Boolean function can be represented by a shellable DNF, we propose a polynomial procedure to compute the dual of a shellable DNF, and we prove that testing the so-called lexico-exchange (LE) property (a strengthening of shellability) is NP-complete.
Disciplines :
Mathematics
Author, co-author :
Boros, Endre
Crama, Yves ; Université de Liège > HEC-Ecole de gestion : UER > Recherche opérationnelle et gestion de la production
Ekin, Oya
Hammer, Peter L.
Ibaraki, Toshihide
Kogan, Alex
Language :
English
Title :
Boolean normal forms, shellability and reliability computations
Ball, M.O., Nemhauser, G.L., Matroids and a reliability analysis problem (1979) Math. Oper. Res., 4, pp. 132-143
Ball, M.O., Provan, J.S., Disjoint products and efficient computation of reliability (1988) Oper. Res., 36, pp. 703-715
Barlow, R.E., Proschan, F., (1975) Statistical Theory of Reliability and Life Testing, , Holt, Rinehart and Winston, New York
Benzaken, C., Crama, Y., Duchet, P., Hammer, P.L., Maffray, F., More characterizations of triangulated graphs (1990) J. Graph Theory, 14, pp. 413-422
Bertolazzi, P., Sassano, A., An O(mn) algorithm for regular set-covering problems (1987) Theoret. Comput. Sci., 54, pp. 237-247
Bioch, J.C., Ibaraki, T., Complexity of identification and dualization of positive Boolean functions (1995) Inform. and Comput., 123, pp. 50-63
Björner, A., Homology and shellability of matroids and geometric lattices (1992) Matroid Applications, pp. 226-283. , N. White, ed., Cambridge University Press, Cambridge, UK
Björner, A., Topological methods (1995) Handbook of Combinatorics, pp. 1819-1872. , R. Graham, M. Grötschel, and L. Lovász, eds., Elsevier, Amsterdam
Boros, E., (1994) Dualization of Aligned Boolean Functions, , RUTCOR Research Report RRR 9-94, Rutgers University, New Brunswick, NJ
Crama, Y., Dualization of regular Boolean functions (1987) Discrete Appl Math., 16, pp. 79-85
Danaraj, G., Klee, V., Which spheres are shellable? (1978) Ann. Discrete Math., 2, pp. 33-52. , Algorithmic Aspects of Combinatorics
Eiter, T., Gottlob, G., Identifying the minimal transversals of a hypergraph and related problems (1995) SIAM J. Comput., 24, pp. 1278-1304
Fredman, M., Khachiyan, L., On the complexity of dualization of monotone disjunctive normal forms (1996) J. Algorithms, 21, pp. 618-628
Garey, M.R., Johnson, D.S., (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness, , W.H. Freeman, New York
Gurvich, V., Khachiyan, L., On Generating the Irredundant Conjunctive and Disjunctive Normal Forms of Monotone Boolean Functions (1999) Discrete Appl. Math., 96-97, pp. 363-373
Klee, V., Kleinschmidt, P., Convex polytopes and related complexes (1995) Handbook of Combinatorics, pp. 875-917. , R. Graham. M. Grötschel, and L. Lovász, eds., Elsevier, Amsterdam
Locks, M.O., Inverting and minimalizing path sets and cut sets (1978) IEEE Trans. Reliability, R-27, pp. 107-109
Locks, M.O., Recursive disjoint products: A review of three algorithms (1982) IEEE Trans. Reliability, R-31, pp. 33-35
Mendelson, E., (1970) Theory and Problems of Boolean Algebra and Switching Circuits, , Schaum's Outline Series, McGraw-Hill, New York, London, Sydney
Muroga, S., (1971) Threshold Logic and Its Applications, , Wiley-Interscience, New York
Provan, J.S., Boolean decomposition schemes and the complexity of reliability computations (1991) DIMACS Ser. Discrete Math., 5, pp. 213-228. , Amer. Math. Soc., Providence, RI
Provan, J.S., Ball, M.O., Efficient recognition of matroid and 2-monotonic systems (1988) Proceedings in Applied Mathematics, 33, pp. 122-134. , Applications of Discrete Mathematics, R.D. Ringeisen and F.S. Roberts, eds., SIAM, Philadelphia, PA
Peled, U.N., Simeone, B., Polynomial time algorithms for regular set-covering and threshold synthesis (1985) Discrete Appl. Math., 12, pp. 57-69
Peled, U.N., Simeone, B., An O(nm)-time algorithm for computing the dual of a regular Boolean function (1994) Discrete Appl. Math., 49, pp. 309-323
Ramamurthy, K.G., (1990) Coherent Structures and Simple Games, , Kluwer Academic Publishers, Dordrecht, The Netherlands
Shier, D.R., Whited, D.E., Algorithms for generating minimal cutsets by inversion (1985) IEEE Trans. Reliability, R-34, pp. 314-318