Reasoning with preference trees over combinatorial domains

Xudong Liu, Miroslaw Truszczynski

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

4 Scopus citations


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
Number of pages16
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)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference4th International Conference on Algorithmic Decision Theory, ADT 2015
Country/TerritoryUnited States

Bibliographical note

Publisher Copyright:
© Springer International Publishing Switzerland 2015.

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


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

Cite this