ALLSAT compressed with wildcards: From CNF's to orthogonal DNF's by imposing the clauses one by one
arXiv:1608.08472
Abstract
We present a novel technique for converting a Boolean CNF into an orthogonal DNF, aka exclusive sum of products. Our method (which will be pitted against a hardwired command from Mathematica) zooms in on the models of the CNF by imposing its clauses one by one. Clausal Imposition invites parallelization, and wildcards beyond the common don't-care symbol compress the output. The method is most efficient for few but large clauses. Generalizing clauses one can in fact impose superclauses. By definition, superclauses are obtained from clauses by substituting each positive litereal by an arbitrary conjunction of positive literals.
arXiv commentTo appear in The Computer Journal
References in corpus (4)
- The joy of implications, aka pure Horn functions: mainly a survey
- Enumeration of Enumeration Algorithms
- Computing the output distribution and selection probabilities of a stack filter from the DNF of its positive Boolean function
- Post-Proceedings of the First International Workshop on Learning and Nonmonotonic Reasoning