Compression with Wildcards: All k-Models of a Binary Decision Diagram

Abstract

A bitstring of length n is an element of {0, 1} n . Further the bitstring (say) (0, 0, 1, 0, 1, 1,0) has Hamming-weight 3, since 3 times "1" occurs. A function of type : {0, 1} n → {0, 1} is a Boolean function, and a bitstring y ∈ {0, 1} n with (y) = 1 is a model of . Given a Binary Decision Diagram B of a Boolean function , it is well known that all N models of can be enumerated in polynomial total time, i.e. in time polynomial in n and |B| and N (here |B| is the size of B). Furthermore, upon using don't-care symbols, the enumeration can be rendered in a compressed fashion. We show that likewise all models of fixed Hamming-weight k can be enumerated in polynomial total time and in compressed fashion.