# Choice Logics and Their Computational Properties

arXiv: https://arxiv.org/abs/2106.05052 · HTML: https://mlsanity.com/paper/2106.05052/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Jun 2021.

## Built on by (most cited first, 3 of 3)

- [Shield Synthesis for LTL Modulo Theories](https://mlsanity.com/paper/2406.04184/) (2024)
- [Strong Equivalence of Logic Programs with Ordered Disjunction: a Logical Perspective](https://mlsanity.com/paper/2205.04882/) (2022)
- [Truth and Preferences -- A Game Approach for Qualitative Choice Logic](https://mlsanity.com/paper/2209.12777/) (2022)

## Abstract (arXiv)

Qualitative Choice Logic (QCL) and Conjunctive Choice Logic (CCL) are formalisms for preference handling, with especially QCL being well established in the field of AI. So far, analyses of these logics need to be done on a case-by-case basis, albeit they share several common features. This calls for a more general choice logic framework, with QCL and CCL as well as some of their derivatives being particular instantiations. We provide such a framework, which allows us, on the one hand, to easily define new choice logics and, on the other hand, to examine properties of different choice logics in a uniform setting. In particular, we investigate strong equivalence, a core concept in non-classical logics for understanding formula simplification, and computational complexity. Our analysis also yields new results for QCL and CCL. For example, we show that the main reasoning task regarding preferred models is Thetap2-complete for QCL and CCL, while being Deltap2-complete for a newly introduced choice logic.