New Compilation Languages Based on Restricted Weak Decomposability
Proceedings of the AAAI Conference on Artificial Intelligence · 11.04.2025 · 39 (14) · 14987-14996
DOI: 10.1609/aaai.v39i14.33643 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the AAAI Conference on Artificial Intelligence, online erschienen am 11.04.2025. Verfasst von Petr Illner. Die Arbeit wurde bisher 1-mal zitiert (Crossref).
Abstract (Originalsprache)
This paper introduces two new compilation languages restricting weak decomposable negation normal form (wDNNF) circuits and integrates them into the knowledge compilation map. Positive (resp. negative) wDNNF circuits restrict wDNNF circuits so that each variable shared among the inputs of a conjunction node can only have positive (resp. negative) occurrences in that subcircuit. Unlike wDNNF circuits, pwDNNF (resp. nwDNNF) circuits satisfy the maximum (resp. minimum) cardinality query. We present a compiler for converting CNF formulae into pwDNNF and nwDNNF circuits by extending Bella - the state-of-the-art compiler for wDNNF circuits. We introduce a new caching scheme, called Cara, that exploits isomorphism. Using that scheme, we show a new compilation method based on copying subcircuits, which may significantly speed up compilations at the expense of increasing circuit sizes. Our experiments demonstrate that nwDNNF circuits are suitable for computing most probable explanations (MPEs) in two-layer Bayesian networks (BNs) with large domains.
Zitieren
APA
Illner, P. (2025). New Compilation Languages Based on Restricted Weak Decomposability. Proceedings of the AAAI Conference on Artificial Intelligence, 39(14), 14987-14996. https://doi.org/10.1609/aaai.v39i14.33643
Vancouver
Illner P. New Compilation Languages Based on Restricted Weak Decomposability. Proceedings of the AAAI Conference on Artificial Intelligence. 2025;39(14):14987-14996. doi:10.1609/aaai.v39i14.33643
BibTeX
@article{Illner2025,
author = {Illner, Petr},
title = {New Compilation Languages Based on Restricted Weak Decomposability},
journal = {Proceedings of the AAAI Conference on Artificial Intelligence},
year = {2025},
volume = {39},
number = {14},
pages = {14987--14996},
doi = {10.1609/aaai.v39i14.33643}
}
EUVIMED