TY - JOUR
T1 - Optimal models of disjunctive logic programs: semantics, complexity, and computation
JF - Knowledge and Data Engineering, IEEE Transactions on
Y1 - 2004
A1 - Leone,N.
A1 - Scarcello,F.
A1 - V.S. Subrahmanian
KW - complexity;
KW - computational
KW - disjunctive
KW - function;
KW - knowledge
KW - LANGUAGE
KW - Logic
KW - minimal
KW - model
KW - nonmonotonic
KW - objective
KW - optimisation;
KW - OPTIMIZATION
KW - problems;
KW - program
KW - Programming
KW - programming;
KW - reasoning;
KW - representation;
KW - semantics;
KW - stable
KW - user-specified
AB - 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 with regard to the semantics the user has in mind. Thus, for example, in the case of stable models [M. Gelfond et al., (1988)], choice models [D. Sacca et al., (1990)], answer sets [M. Gelfond et al., (1991)], 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 U_{1} may prefer model M_{1} isin;SEM(P) to model M_{2} isin;SEM(P) based on some evaluation criterion that she has. We develop a logic program semantics based on optimal models. This semantics does not add yet another semantics to the logic programming arena - it takes as input an existing semantics SEM(P) and a user-specified objective function Obj, and yields a new semantics Opt(P)_ sube; SEM(P) that realizes the objective function within the framework of preferred models identified already by SEM(P). 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, 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.
VL - 16
SN - 1041-4347
CP - 4
M3 - 10.1109/TKDE.2004.1269672
ER -