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

• scientific article; zbMATH DE number 1946853 (Why is no real title available?)
• CV-width: a new complexity parameter for CNFs
• Cliquewidth and knowledge compilation
• Decomposable negation normal form
• 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)

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

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)