On compiling CNFs into structured deterministic DNNFs

DOI10.1007/978-3-319-24318-4_15MaRDI QIDQ3453225zbMATH OpenOpenAlexFDO

Authors Simone Bova, Florent Capelli, Stefan Mengel, Friedrich Slivovsky

Publication date 20 November 2015

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-24318-4_15

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• Parameterized compilation lower bounds for restricted CNF-formulas
• Top-down algorithms for constructing structured DNNF: theoretical and practical implications
• CV-width: a new complexity parameter for CNFs
• Decomposable negation normal form
• On limitations of structured (deterministic) DNNFs

Cites work

• Cliquewidth and knowledge compilation
• CV-width: a new complexity parameter for CNFs
• Decomposable negation normal form
• scientific article; zbMATH DE number 1946853 (Why is no real title available?)
• Model counting for formulas of bounded clique-width
• On the Tractable Counting of Theory Models and its Application to Truth Maintenance and Belief Revision
• Parametrized complexity theory.
• Satisfiability of acyclic and almost acyclic CNF formulas
• Solving MaxSAT and \#SAT on structured CNF formulas
• Top-down algorithms for constructing structured DNNF: theoretical and practical implications
• Understanding model counting for -acyclic CNF-formulas

Cited in

(19)

• On the relation between structured \(d\)-DNNFs and SDDs
• Approximate weighted model integration on DNF structures
• On compiling structured CNFs to OBDDs
• Lower bounds on the mim-width of some graph classes
• Parameterized compilation lower bounds for restricted CNF-formulas
• Top-down algorithms for constructing structured DNNF: theoretical and practical implications
• On compiling structured CNFs to OBDDs
• Connecting width and structure in knowledge compilation
• On the Tractable Counting of Theory Models and its Application to Truth Maintenance and Belief Revision
• Fixed parameter tractable optimization under DNNF constraints
• Tractable QBF by knowledge compilation
• Tableaux, path dissolution, and decomposable negation normal form for knowledge compilation
• CV-width: a new complexity parameter for CNFs
• Decomposable negation normal form
• DAG-\( \Sigma \): a DAG-based sigma protocol for relations in CNF
• An Abstract CNF-to-d-DNNF Compiler Based on Chronological CDCL
• Reasoning with propositional logic: from SAT solvers to knowledge compilation
• Direct access for conjunctive queries with negations
• On limitations of structured (deterministic) DNNFs

This page was built for publication: On compiling CNFs into structured deterministic DNNFs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3453225)