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.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 | Contatta l'autore |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.