CV-width: a new complexity parameter for CNFs

MaRDI QIDQ5283031zbMATH OpenFDO

Authors Umut Oztok, Adnan Darwiche

Publication date 18 July 2017

Full work available at URL http://ebooks.iospress.nl/volumearticle/37019

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Classical propositional logic (03B05)

Recommendations

• Parameterized compilation lower bounds for restricted CNF-formulas
• On compiling CNFs into structured deterministic DNNFs
• On compiling structured CNFs to OBDDs
• On compiling structured CNFs to OBDDs
• Connecting knowledge compilation classes and width parameters

Cited in

(9)

• On compiling structured CNFs to OBDDs
• Parameterized compilation lower bounds for restricted CNF-formulas
• On compiling structured CNFs to OBDDs
• Graph width measures for CNF-encodings with auxiliary variables
• Revisiting graph width measures for CNF-encodings
• Functional Treewidth: Bounding Complexity in the Presence of Functional Dependencies
• An Abstract CNF-to-d-DNNF Compiler Based on Chronological CDCL
• On compiling CNFs into structured deterministic DNNFs
• Connecting width and structure in knowledge compilation

This page was built for publication: CV-width: a new complexity parameter for CNFs

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