Max-ASP: Maximum Satisfiability of Answer Set Programs (2009)
AUTHORS:
Oikarinen Emilia
,
Järvisalo Matti
BOOKTITLE:
Proceedings of the 10th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR 2009)
SERIES:
Lecture Notes in Computer Science
VOLUME:
5753
PAGES:
236--249
URL:
http://www.tcs.tkk.fi/~mjj/publications.shtml
@inproceedings{ OikarinenJ:LPNMR09, editor = "Erdem, Esra and Lin, Fangzhen and Schaub, Torsten", author = {Oikarinen, Emilia and J\"arvisalo, Matti}, publisher = "Springer", title = "{Max-ASP}: Maximum Satisfiability of Answer Set Programs", url = "http://www.tcs.tkk.fi/~mjj/publications.shtml", series = "Lecture Notes in Computer Science", booktitle = "Proceedings of the 10th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR 2009)", abstract = "This paper studies answer set programming (ASP) in the generalized context of soft constraints and optimization criteria. In analogy to the well-known Max-SAT problem of maximum satisfiability of propositional formulas, we introduce the problems of unweighted and weighted Max-ASP. Given a normal logic program $P$, in Max-ASP the goal is to find so called optimal Max-ASP models, which minimize the total cost of unsatisfied rules in $P$ and are at the same time answer sets for the set of satisfied rules in $P$. Inference rules for Max-ASP are developed, resulting in a complete branch-and-bound algorithm for finding optimal models for weighted Max-ASP instances. Differences between the Max-ASP problem and earlier proposed related concepts in the context of ASP are also discussed. Furthermore, translations between Max-ASP and Max-SAT are studied.", volume = "5753", flags = "public MCM copy", year = "2009", pages = "236--249" }