An extended Knowledge Compilation Map for Conditional Preference Statements-based and Generalized Additive Utilities-based Languages - IRIT - Université Toulouse III Paul Sabatier Access content directly
Reports Year : 2023

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

Abstract

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, and introduce a new parameterized family of languages, which enables to balance expressiveness against the complexity of some queries. This paper is an extended version of [29]-in addition to the results of [29], it contains a study of several transformations (Section 7). We have also added the GAI language to the map.
Fichier principal
Vignette du fichier
FargierMengelMengin_irit23.pdf (799.37 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-04356562 , version 1 (20-12-2023)

Identifiers

  • HAL Id : hal-04356562 , version 1

Cite

Hélène Fargier, Stefan Mengel, Jérôme Mengin. An extended Knowledge Compilation Map for Conditional Preference Statements-based and Generalized Additive Utilities-based Languages. RR–2023–03–FR, Institut de recherche en informatique de Toulouse (IRIT). 2023. ⟨hal-04356562⟩
107 View
11 Download

Share

Gmail Facebook X LinkedIn More