Compression with Wildcards: From CNFs to Orthogonal DNFs by Imposing the Clauses One-by-One
| Autor: | Marcel Wild |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
General Computer Science
010201 computation theory & mathematics Computer science Compression (functional analysis) 0211 other engineering and technologies 021107 urban & regional planning Wildcard character 0102 computer and information sciences 02 engineering and technology computer.file_format 01 natural sciences computer Algorithm |
| Zdroj: | The Computer Journal. 65:1073-1087 |
| ISSN: | 1460-2067 0010-4620 |
| DOI: | 10.1093/comjnl/bxaa142 |
| Popis: | We present a novel technique for converting a Boolean conjunctive normal form (CNF) into an orthogonal disjunctive normal form (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 literal by an arbitrary conjunction of positive literals. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|