Pruning Boolean d-DNNF Circuits Through Tseitin-Awareness
<|reference_start|>Pruning Boolean d-DNNF Circuits Through Tseitin-Awareness: Boolean circuits in d-DNNF form enable tractable probabilistic inference. However, as a key insight of this work, we show that commonly used d-DNNF compilation approaches introduce irrelevant subcircuits. We call these subcircuits Tseitin artifacts, as they are introduced due to the Tseitin transformation step -- a well-established procedure to transform any circuit into the CNF format required by several d-DNNF knowledge compilers. We discuss how to detect and remove both Tseitin variables and Tseitin artifacts, leading to more succinct circuits. We empirically observe an average size reduction of 77.5% when removing both Tseitin variables and artifacts. The additional pruning of Tseitin artifacts reduces the size by 22.2% on average. This significantly improves downstream tasks that benefit from a more succinct circuit, e.g., probabilistic inference tasks.<|reference_end|>
@article{derkinderen2024pruning,
    title={Pruning Boolean d-DNNF Circuits Through Tseitin-Awareness},
    author={Vincent Derkinderen},
    journal={arXiv preprint arXiv:2407.17951},
    year={2024},
    archivePrefix={arXiv},
    eprint={2407.17951},
    primaryClass={cs.AI cs.LO}
}