Pruning Boolean d-DNNF Circuits Through Tseitin-Awareness

Autor:	Derkinderen, Vincent
Rok vydání:	2024
Předmět:	Computer Science - Artificial Intelligence Computer Science - Logic in Computer Science
Druh dokumentu:	Working Paper
Popis:	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. Comment: submitted to ICTAI 2024
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2407.17951 Zobrazit plný text záznamu View this record from Arxiv