No full text
Article (Scientific journals)
Boolean normal forms, shellability and reliability computations
Boros, Endre; Crama, Yves; Ekin, Oya et al.
2000In SIAM Journal on Discrete Mathematics, 13, p. 212-226
Peer Reviewed verified by ORBi
 

Files


Full Text
No document available.

Send to



Details



Keywords :
Boolean functions; orthogonal DNFs; dualization; shellability; reliability
Abstract :
[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
Publication date :
2000
Journal title :
SIAM Journal on Discrete Mathematics
ISSN :
0895-4801
eISSN :
1095-7146
Publisher :
Society for Industrial & Applied Mathematics
Volume :
13
Pages :
212-226
Peer reviewed :
Peer Reviewed verified by ORBi
Available on ORBi :
since 07 October 2016

Statistics


Number of views
43 (1 by ULiège)
Number of downloads
0 (0 by ULiège)

Scopus citations®
 
9
Scopus citations®
without self-citations
9
OpenCitations
 
8

Bibliography


Similar publications



Contact ORBi