On optimal solutions of answer set optimization problems

Ying Zhu; Miroslaw Truszczynski

doi:10.1007/978-3-642-40564-8_55

On optimal solutions of answer set optimization problems

Ying Zhu, Miroslaw Truszczynski

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

7 Scopus citations

Abstract

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.

Original language	English
Title of host publication	Logic Programming and Nonmonotonic Reasoning - 12th International Conference, LPNMR 2013, Proceedings
Pages	556-568
Number of pages	13
DOIs	https://doi.org/10.1007/978-3-642-40564-8_55
State	Published - 2013
Event	12th International Conference on Logic Programming and Nonmonotonic Reasoning, LPNMR 2013 - Corunna, Spain Duration: Sep 15 2013 → Sep 19 2013

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	8148 LNAI
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	12th International Conference on Logic Programming and Nonmonotonic Reasoning, LPNMR 2013
Country/Territory	Spain
City	Corunna
Period	9/15/13 → 9/19/13

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

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

Cite this

Zhu, Y., & Truszczynski, M. (2013). On optimal solutions of answer set optimization problems. In Logic Programming and Nonmonotonic Reasoning - 12th International Conference, LPNMR 2013, Proceedings (pp. 556-568). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8148 LNAI). https://doi.org/10.1007/978-3-642-40564-8_55

@inproceedings{4a0ee28dffde451f8a2267208431e3c8,

title = "On optimal solutions of answer set optimization problems",

abstract = "In 2003, Brewka, Niemel{\"a} 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.",

author = "Ying Zhu and Miroslaw Truszczynski",

year = "2013",

doi = "10.1007/978-3-642-40564-8_55",

language = "English",

isbn = "9783642405631",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "556--568",

booktitle = "Logic Programming and Nonmonotonic Reasoning - 12th International Conference, LPNMR 2013, Proceedings",

note = "12th International Conference on Logic Programming and Nonmonotonic Reasoning, LPNMR 2013 ; Conference date: 15-09-2013 Through 19-09-2013",

}

Zhu, Y & Truszczynski, M 2013, On optimal solutions of answer set optimization problems. in Logic Programming and Nonmonotonic Reasoning - 12th International Conference, LPNMR 2013, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8148 LNAI, pp. 556-568, 12th International Conference on Logic Programming and Nonmonotonic Reasoning, LPNMR 2013, Corunna, Spain, 9/15/13. https://doi.org/10.1007/978-3-642-40564-8_55

On optimal solutions of answer set optimization problems. / Zhu, Ying; Truszczynski, Miroslaw.
Logic Programming and Nonmonotonic Reasoning - 12th International Conference, LPNMR 2013, Proceedings. 2013. p. 556-568 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8148 LNAI).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

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 -

Zhu Y, Truszczynski M. On optimal solutions of answer set optimization problems. In Logic Programming and Nonmonotonic Reasoning - 12th International Conference, LPNMR 2013, Proceedings. 2013. p. 556-568. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-40564-8_55

On optimal solutions of answer set optimization problems

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this