TY - GEN

T1 - On optimal solutions of answer set optimization problems

AU - Zhu, Ying

AU - Truszczynski, Miroslaw

PY - 2013

Y1 - 2013

N2 - In 2003, Brewka, Niemelä and Truszczynski introduced answer-set optimization problems. They consist of two components: a logic program and a set of preference rules. Answer sets of the program represent possible outcomes; preferences determine a preorder on them. Of interest are answer sets of the program that are optimal with respect to the preferences. In this work, we consider computational problems concerning optimal answer sets. We implement and study several methods for the problems of computing an optimal answer set; computing another one, once the first one is found; and computing an optimal answer set that is similar to (respectively, dissimilar from) a given interpretation. For the problems of the existence of similar and dissimilar optimal answer set we establish their computational complexity.

AB - In 2003, Brewka, Niemelä and Truszczynski introduced answer-set optimization problems. They consist of two components: a logic program and a set of preference rules. Answer sets of the program represent possible outcomes; preferences determine a preorder on them. Of interest are answer sets of the program that are optimal with respect to the preferences. In this work, we consider computational problems concerning optimal answer sets. We implement and study several methods for the problems of computing an optimal answer set; computing another one, once the first one is found; and computing an optimal answer set that is similar to (respectively, dissimilar from) a given interpretation. For the problems of the existence of similar and dissimilar optimal answer set we establish their computational complexity.

UR - http://www.scopus.com/inward/record.url?scp=84885813608&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84885813608&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-40564-8_55

DO - 10.1007/978-3-642-40564-8_55

M3 - Conference contribution

AN - SCOPUS:84885813608

SN - 9783642405631

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 556

EP - 568

BT - Logic Programming and Nonmonotonic Reasoning - 12th International Conference, LPNMR 2013, Proceedings

T2 - 12th International Conference on Logic Programming and Nonmonotonic Reasoning, LPNMR 2013

Y2 - 15 September 2013 through 19 September 2013

ER -