Affiliations: Department of Mathematics and Computer Science, University of Calabria, Via Pietro Bucci, Rende (CS), Italy
Corresponding author: Mario Alviano, Department of Mathematics and Computer Science, University of Calabria, Via Pietro Bucci 30/B, 87036 Rende (CS), Italy. E-mail: [email protected].
Note:  This research has been partially supported by the Italian Ministry for Economic Development (MISE) under project “PIUCultura – Paradigmi Innovativi per l’Utilizzo della Cultura” (n. F/020016/01-02/X27), and under project “Smarter Solutions in the Big Data World (S2BDW)” (n. F/050389/01-03/X32) funded within the call “HORIZON2020” PON I&C 2014-2020, and by Gruppo Nazionale per il Calcolo Scientifico (GNCS-INdAM). An extended abstract of this work was already published .
Abstract: Answer set programming (ASP) is a declarative language for nonmonotonic reasoning based on stable model semantics. A stable model is a classical model of the input program satisfying the following stability condition: only necessary information is included in the model under the assumptions provided by the model itself for the unknown knowledge in the program, where unknown knowledge is encoded by means of default negation. Rational agents acting in the real world often have to reason in presence of unknown knowledge. It is also common that real world agents cannot meet all their desiderata. For this reason, ASP programs may include weak constraints for representing numerical preferences over jointly incompatible conditions. Stable models are therefore associated with a cost given by the unsatisfied weak constraints, and stable models of minimum cost are preferred. This paper summarizes algorithms and strategies for computing optimal stable models, and hints on how these algorithms can be extended to handle some qualitative preferences that have a natural representation in circumscription, that is, those based on subset-minimality and superset-maximality.
Keywords: Answer set programming, boolean optimization, unsatisfiable core analysis, circumscription