Compilation and Fast Model Counting beyond CNF
Authors: Alexis de Colnet, Stefan Szeider, Tianwei Zhang
IJCAI 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | This paper strengthens our theoretical knowledge of what classes of functions can be efficiently transformed, or compiled, into d-DNNF. Our main contribution is the fixedparameter tractable (FPT) compilation of conjunctions of specific constraints parameterized by incidence treewidth. This subsumes the known result for CNF. The running time of the FPT compilation is singly exponential in the incidence treewidth but hides large constants in the exponent. To balance that, we give a more efficient FPT algorithm for model counting that applies to a sub-family of the constraints and does not require compilation. We prove our theorem in Section 4 with a more accurate running time where the exponential part also depends on w. |
| Researcher Affiliation | Academia | Algorithms and Complexity Group, TU Wien, Vienna, Austria |
| Pseudocode | No | The paper describes algorithms in narrative text but does not include structured pseudocode or algorithm blocks (e.g., labeled 'Algorithm X' or formatted code-like steps). |
| Open Source Code | No | The paper does not provide any concrete access information (specific repository link, explicit code release statement, or code in supplementary materials) for the source code of the methodology described. |
| Open Datasets | No | The paper is theoretical and does not conduct experiments involving datasets for training or evaluation. Therefore, it does not provide concrete access information for a publicly available or open dataset. |
| Dataset Splits | No | The paper is theoretical and does not describe experiments that involve dataset partitioning. Therefore, it does not provide specific dataset split information. |
| Hardware Specification | No | The paper is theoretical and does not describe empirical experiments. Therefore, it does not provide specific hardware details used for running experiments. |
| Software Dependencies | No | The paper does not provide specific ancillary software details, such as library or solver names with version numbers, needed to replicate the theoretical constructs or potential implementations. |
| Experiment Setup | No | The paper is theoretical and does not describe empirical experiments. Therefore, it does not contain specific experimental setup details like hyperparameter values or training configurations. |