TCS / Research / Publications / Max-ASP: Maximum Satisfiability of Answer Set Programs
Helsinki University of Technology, 
     Laboratory for Theoretical Computer Science

Max-ASP: Maximum Satisfiability of Answer Set Programs

Reference:

Emilia Oikarinen and Matti Järvisalo. Max-ASP: Maximum satisfiability of answer set programs. In Esra Erdem, Fangzhen Lin, and Torsten Schaub, editors, Proceedings of the 10th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR 2009), volume 5753 of Lecture Notes in Computer Science, pages 236–249. Springer, 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 , in Max-ASP the goal is to find so called optimal Max-ASP models, which minimize the total cost of unsatisfied rules in and are at the same time answer sets for the set of satisfied rules in . 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.

Suggested BibTeX entry:

@inproceedings{OikarinenJ:LPNMR09,
    author = {Emilia Oikarinen and Matti J\"arvisalo},
    booktitle = {Proceedings of the 10th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR 2009)},
    editor = {Esra Erdem and Fangzhen Lin and Torsten Schaub},
    pages = {236--249},
    publisher = {Springer},
    series = {Lecture Notes in Computer Science},
    title = {{Max-ASP}: Maximum Satisfiability of Answer Set Programs},
    volume = {5753},
    year = {2009},
}

See www.tcs.tkk.fi ...

[TCS main] [Contact Info] [Personnel] [Research] [Publications] [Software] [Studies] [News Archive] [Links]
Latest update: 19 January 2010.