Polynomial approximations of Boolean functions by means of positive binary decision diagrams

摘要

In this paper, we introduce the concept of positive Binary Decision Diagrams (p-BDDs). p-BDDs can be used to compute monotone approximation of Boolean functions in polynomial time. We show, by assessing both qualitatively and quantitatively real life fault trees, that thses approximations are accurate. The presented results are a new contribution to the design of a corpus of efficient BDD-based algorothms to handle Boolean risk assessment models.