Optimal Models of Disjunctive Logic Programs: Semantics, Complexity, and Computation
Optimal Models of Disjunctive Logic Programs: Semantics, Complexity, and Computation
Files
Publication or External Link
Date
2001-11-01
Authors
Leone, Nicola
Scarcello, Francesco
Subrahmanian, V. S.
Advisor
Citation
DRUM DOI
Abstract
Almost all semantics for logic programs with negation identify a set,
SEM(P), of models of program P, as the intended semantics of P, and
any model M in this class is considered a possible meaning of P w.r.t. the
semantics the user has in mind. Thus, for example, in the case of stable
models, choice models,
answer sets, etc.,
different possible models correspond to different ways of ``completing'' the
incomplete information in the logic program.
However, different end-users may have
different ideas on which of these different models in SEM(P) is a
reasonable one from their point of view. For instance, given SEM(P), user
U1 may prefer model M1 to model M2
based on some evaluation criterion that she has. In this paper, we will
develop a notion of logic program semantics based on the concept of an
Optimal Model. This semantics doesn't add yet another semantics to thelogic programming arena -- rather, it takes as input, an existing semantics
SEM(P) and a user-specified objective function Obj, and yields
a new semantics that realizes the
objective
function within the framework of preferred models
identified already by SEM(P) in different ways.
Thus, the user who may or may not know anything about logic
programming has considerable flexibility in making the system reflect
her own objectives by building ``on top'' of existing semantics known to the
system. In addition to the declarative semantics characterization, we provide a complete complexity analysis and
algorithms to compute optimal models under varied conditions
when SEM(P) is the stable model
semantics, the minimal models semantics, and the all-models semantics.