Reasoning with preference trees over combinatorial domains

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

3 Scopus citations

Abstract

Preference trees, or P-trees for short, offer an intuitive and often concise way of representing preferences over combinatorial domains. In this paper, we propose an alternative definition of P-trees, and formally introduce their compact representation that exploits occurrences of identical subtrees. We show that P-trees generalize lexicographic preference trees and are strictly more expressive. We relate P-trees to answerset optimization programs and possibilistic logic theories. Finally, we study reasoning with P-trees and establish computational complexity results for the key reasoning tasks of comparing outcomes with respect to orders defined by P-trees, and of finding optimal outcomes.

Original languageEnglish
Title of host publicationAlgorithmic Decision Theory - 4th International Conference, ADT 2015, Proceedings
EditorsToby Walsh
Pages19-34
Number of pages16
DOIs
StatePublished - 2015
Event4th International Conference on Algorithmic Decision Theory, ADT 2015 - Lexington, United States
Duration: Sep 27 2015Sep 30 2015

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9346
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference4th International Conference on Algorithmic Decision Theory, ADT 2015
Country/TerritoryUnited States
CityLexington
Period9/27/159/30/15

Bibliographical note

Publisher Copyright:
© Springer International Publishing Switzerland 2015.

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science (all)

Fingerprint

Dive into the research topics of 'Reasoning with preference trees over combinatorial domains'. Together they form a unique fingerprint.

Cite this