On limitations of structured (deterministic) DNNFs
From MaRDI portal
Publication:778525
DOI10.1007/S00224-019-09960-WzbMATH Open1446.68152OpenAlexW2993167090MaRDI QIDQ778525FDOQ778525
Authors: Beate Bollig, Matthias Buttkus 
Publication date: 2 July 2020
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00224-019-09960-w
Recommendations
- On compiling CNFs into structured deterministic DNNFs
- On deterministic approximation of DNF
- On the relation between structured \(d\)-DNNFs and SDDs
- Top-down algorithms for constructing structured DNNF: theoretical and practical implications
- Limitations of lower bound methods for deterministic nested word automata
- scientific article; zbMATH DE number 4049104
- On the impossibility of structure-preserving deterministic primitives
- On the impossibility of structure-preserving deterministic primitives
- scientific article; zbMATH DE number 1332665
- Recognition of tractable DNFs representable by a constant number of intervals
complexity theoryordered binary decision diagramsknowledge compilationdecomposable negation normal formssentential decision diagrams
Cites Work
- Graph-Based Algorithms for Boolean Function Manipulation
- Branching Programs and Binary Decision Diagrams
- Title not available (Why is that?)
- On the complexity of VLSI implementations and graph representations of Boolean functions with application to integer multiplication
- On the read-once property of branching programs and CNFs of bounded treewidth
- Title not available (Why is that?)
- Decomposable negation normal form
- On the Complexity of the Hidden Weighted Bit Function for Various BDD Models
- Knowledge compilation meets database theory: compiling queries to decision diagrams
- On the relative succinctness of sentential decision diagrams
- On oblivious branching programs with bounded repetition that cannot efficiently compute CNFs of bounded treewidth
Cited In (5)
- On the relative succinctness of sentential decision diagrams
- Top-down algorithms for constructing structured DNNF: theoretical and practical implications
- An Abstract CNF-to-d-DNNF Compiler Based on Chronological CDCL
- On compiling CNFs into structured deterministic DNNFs
- On the relation between structured \(d\)-DNNFs and SDDs
This page was built for publication: On limitations of structured (deterministic) DNNFs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q778525)
