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 P, user U1 may prefer model M1 to model M2 based on some evaluation criterion that she has. In this paper, we develop a logic program semantics based on "Optimal Models". This semantics doesn’t 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) (subset of 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.

Optimal Models of Disjunctive Logic Programs: Semantics, Complexity, and Computation

LEONE, Nicola;SCARCELLO, Francesco;
2004-01-01

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 P, user U1 may prefer model M1 to model M2 based on some evaluation criterion that she has. In this paper, we develop a logic program semantics based on "Optimal Models". This semantics doesn’t 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) (subset of 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.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.11770/129621
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 6
  • ???jsp.display-item.citation.isi??? 7
social impact