Several logical languages have been studied in AI for encoding compactly preference relations over a set of alternatives. In this paper, we analyze how succinctly a preference relation can be expressed in those languages: after identifying the sets of preference relations expressed by several preference languages, we study their relative succinctness by giving some polynomial-size translations in some cases, and proving the impossibility of such translations in other cases.

Expressive power and succinctness of propositional languages for preference representation / SYLVIE COSTE, Marquis; Jerome, Lang; Liberatore, Paolo; Pierre, Marquis. - STAMPA. - (2004), pp. 203-212.

Expressive power and succinctness of propositional languages for preference representation

LIBERATORE, Paolo;
2004

Abstract

Several logical languages have been studied in AI for encoding compactly preference relations over a set of alternatives. In this paper, we analyze how succinctly a preference relation can be expressed in those languages: after identifying the sets of preference relations expressed by several preference languages, we study their relative succinctness by giving some polynomial-size translations in some cases, and proving the impossibility of such translations in other cases.
1577351991
File allegati a questo prodotto
File Dimensione Formato  
VE_2004_11573-206821.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 1.18 MB
Formato Adobe PDF
1.18 MB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/206821
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact