Optimal models of disjunctive-logic 'programs: Semantics, complexity, and computation

Nicola Leone

doi:10.1109/TKDE.2004.1269672

2004-04-01

PRE

Nicola Leone

Francesco Scarcello

V. S. Subrahmanian

DOI：10.1109/TKDE.2004.1269672

原文链接

原文求助

摘要

En 中文

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 [10], choice models [30], answer sets [11], 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 Ion which of these different models in SEM(P) is a reasonable one from their point of view. For instance, given SEM(P), user U, may prefer model M-1 is an element of SEM(P) to model M-2 is an element of SEM(P) based on some evaluation criterion that she has. In this paper, 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 SE-All(P) and a user-specified objective function Obj, and yields a new semantics (Opt) under bar (P) subset of or equal to 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.

Keyword:

disjunctive logic programming

computational complexity

nonmonotonic reasoning

knowledge representation

optimization problems