# An extended Knowledge Compilation Map for Conditional Preference Statements-based and Generalized Additive Utilities-based Languages

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 55 references that are in the map.
- First posted on arXiv 8 Feb 2021.

## Builds on (most cited first, 4 of 4)

- [Reasoning With Conditional Ceteris Paribus Preference Statem](https://mlsanity.com/paper/1301.6681/) (2013)
- [The Computational Complexity of Dominance and Consistency in CP-Nets](https://mlsanity.com/paper/1401.3453/) (2014)
- [Graphical Models for Preference and Utility](https://mlsanity.com/paper/1302.4928/) (2013)
- [Complexity Results for Preference Aggregation over (m)CP-nets: Pareto and Majority Voting](https://mlsanity.com/paper/1806.10018/) (2018)

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

- [A canonical generalization of OBDD](https://mlsanity.com/paper/2604.05537/) (2026)

## Abstract (arXiv)

Conditional preference statements have been used to compactly represent preferences over combinatorial domains. They are at the core of CP-nets and their generalizations, and lexicographic preference trees. Several works have addressed the complexity of some queries (optimization, dominance in particular). We extend in this paper some of these results, and study other queries which have not been addressed so far, like equivalence, and transformations, like conditioning and variable elimination, thereby contributing to a knowledge compilation map for languages based on conditional preference statements. We also study the expressiveness and complexity of queries and transformations for generalized additive utilities.