Skip to Main content Skip to Navigation
Conference papers

On the Use of Partially Ordered Decision Graphs for Knowledge Compilation and Quantified Boolean Formulae

Abstract : Decomposable Negation Normal Form formulae DNNFs form an interesting propositional fragment, both for efficiency and succinctness reasons. A famous subclass of the DNNF fragment is the OBDD fragment which offers many polytime queries and transformations, including quantifier eliminations (under some ordering restrictions). Nevertheless, the decomposable AND nodes at work in OBDDs enable only sequential decisions: clusters of variables are never assigned "in parallel" like in full DNNFs. This is an serious drawback since succinctness for the full t DNNF fragment relies on such a "parallelization property". This is why we suggest to go a step further, from (sequentially) ordered decision diagrams to (partially) ordered, decomposable decision graphs, in which any decomposable AND node is allowed, and not only assignment ones. We show that, like the OBDD fragment, such a new class offers many tractable queries and transformations, including quantifier eliminations under some ordering restrictions. Furthermore, we show that this class is strictly more succinct than OBDD.
Document type :
Conference papers
Complete list of metadata

https://hal-univ-artois.archives-ouvertes.fr/hal-03300967
Contributor : Fabien Delorme <>
Submitted on : Tuesday, July 27, 2021 - 12:38:16 PM
Last modification on : Thursday, September 9, 2021 - 3:10:33 PM

Identifiers

  • HAL Id : hal-03300967, version 1

Citation

Hélène Fargier, Pierre Marquis. On the Use of Partially Ordered Decision Graphs for Knowledge Compilation and Quantified Boolean Formulae. 21th National Conference on Artificial Intelligence (AAAI 2006), AAAI: Association for the Advancement of Artificial Intelligence, Jul 2006, Boston, Massachusetts, United States. pp.42-47. ⟨hal-03300967⟩

Share

Metrics

Record views

13