Structured d-DNNF Is Not Closed under Negation
Authors: Harry Vinall-Smeeth
IJCAI 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Our proof of Theorem 2 exploits a connection between knowledge compilation and communication complexity which has been widely deployed in recent years, see e.g. [Beame and Liew, 2015; Bova et al., 2016; Amarilli et al., 2020]. We start from the same piece of communication complexity as [G o os et al., 2022], where an analogous result for unambiguous finite automata (UFA) is obtained. However, while the size of UFAs is related to the fixed partition communication complexity model the size of structured d-DNNF is related to another model: the best partition communication complexity. We therefore adapt an ingenious construction from [Knop, 2017], which allows one to lift results from the fixed partition model to the best partition model. |
| Researcher Affiliation | Academia | Harry Vinall-Smeeth Technische Universit at Ilmenau, Germany harry.vinall-smeeth@tu-ilmenau.de |
| Pseudocode | No | The paper does not contain structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide any concrete access information (e.g., repository link, explicit statement) for source code. |
| Open Datasets | No | The paper is theoretical and does not mention datasets, training, or data splits. |
| Dataset Splits | No | The paper is theoretical and does not mention datasets, validation, or data splits. |
| Hardware Specification | No | The paper is theoretical and does not mention any hardware specifications used for experiments. |
| Software Dependencies | No | The paper is theoretical and does not mention any specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe any experimental setup details such as hyperparameters or training configurations. |