Compression with wildcards: All models of a Boolean 2-CNF

Marcel Wild

Let $W$ be a finite set which simultaneously serves as the universe of any poset $(W,\preceq)$ and as the vertex set of any graph $G$. Our algorithm, abbreviated A-I-I, enumerates (in a compressed format using don't-care symbols) all $G$-independent order ideals of $(W,\preceq)$. The A-I-I extends to a polynomial total time algorithm that enumerates the modelset of any Boolean 2-CNF. For many instances the high-end Mathematica implementation of A-I-I compares favorably to two competing (hardwired) Mathematica commands. Furthermore, for important special cases of 2-CNF a compression of the modelset that goes beyond don't-cares is possible.

Knowledge Graph



Sign up or login to leave a comment