Choice Logics and Their Computational Properties
Authors: Michael Bernreiter, Jan Maly, Stefan Woltran
IJCAI 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we propose a general framework for choice logics that, on the one hand, makes it easy to define new choice logics by specifying one or more choice connectives and, on the other hand, allows us to settle open questions regarding the computational properties of QCL and CCL in a uniform way. In detail, our main contributions are as follows: We formally define a framework that captures both QCL and CCL, as well as infinitely many new related logics. To showcase the versatility of our framework we explicitly introduce two such new logics called Lexicographic Choice Logic (LCL) and Simple Conjunctive Choice Logic (SCCL). We characterize strong equivalence via simpler equivalence notions for large classes of choice logics. This further enables us to analyze properties related to strong equivalence more easily, and also provides valuable insights into the nature of choice logics. We analyze the computational complexity of choice logics in detail. |
| Researcher Affiliation | Academia | Michael Bernreiter , Jan Maly and Stefan Woltran Institute of Logic and Computation, TU Wien, Austria {mbernrei, jmaly, woltran}@dbai.tuwien.ac.at |
| Pseudocode | No | The paper does not contain structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper mentions 'ASP encodings have been provided in [Bernreiter et al., 2020]' as related work, but there is no explicit statement or link providing open-source code for the methodology described in this paper. |
| Open Datasets | No | This is a theoretical paper that does not involve empirical experiments with datasets, and thus provides no concrete access information for a publicly available or open dataset. |
| Dataset Splits | No | This is a theoretical paper that does not involve empirical experiments with datasets, and thus provides no specific dataset split information. |
| Hardware Specification | No | This is a theoretical paper. It does not describe any specific hardware used for running experiments. |
| Software Dependencies | No | This is a theoretical paper. It does not list specific software dependencies with version numbers for experimental reproducibility. |
| Experiment Setup | No | This is a theoretical paper. It does not describe any experimental setup details, hyperparameters, or training configurations. |