Skip to Main content Skip to Navigation
Reports

A Knowledge Compilation Map for Conditional Preference Statements-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, thereby contributing to a knowledge compilation map for languages based on conditional preference statements. We also introduce a new parameterised family of languages, which enables to balance expressiveness against the complexity of some queries.
Complete list of metadata

https://hal.archives-ouvertes.fr/hal-03133187
Contributor : Jérôme Mengin <>
Submitted on : Monday, February 8, 2021 - 10:47:04 AM
Last modification on : Thursday, March 18, 2021 - 2:25:24 PM

Files

compil-prefs.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-03133187, version 1
  • ARXIV : 2102.04107

Citation

Hélène Fargier, Jérôme Mengin. A Knowledge Compilation Map for Conditional Preference Statements-based Languages. [Research Report] IRIT/RR--2021--02--FR, Institut de Recherche en Informatique de Toulouse (CNRS : UMR5505; INPT de Toulouse; Universités de Toulouse I, II et III). 2021. ⟨hal-03133187⟩

Share

Metrics

Record views

196

Files downloads

28