The partial stable models of a logic program form a class of models that include the (unique) well-founded model, total stable models and other two interesting subclasses: maximal stable models and least undefined stable models. As stable models different from the well-founded are not unique, DATALOG: queries do not in general correspond to functions. The question is: what are the expressive powers of the various types of stable models when they are restricted to the class of all functional queries? The paper shows that this power does not go in practice beyond the one of stratified queries, except for least undefined stable models which, instead, capture the whole Boolean hierarchy BH. Finally, it is illustrated how the latter result can be used to design a “functional” language which, by means of a disciplined usage of negation, allows to achieve the desired level of expressiveness up to BH so that exponential time resolution is eventually enabled only for hard problems.

"Possible is Certain" is Desiderable and can be Expressive

GRECO, Sergio;SACCÀ D.
1997-01-01

Abstract

The partial stable models of a logic program form a class of models that include the (unique) well-founded model, total stable models and other two interesting subclasses: maximal stable models and least undefined stable models. As stable models different from the well-founded are not unique, DATALOG: queries do not in general correspond to functions. The question is: what are the expressive powers of the various types of stable models when they are restricted to the class of all functional queries? The paper shows that this power does not go in practice beyond the one of stratified queries, except for least undefined stable models which, instead, capture the whole Boolean hierarchy BH. Finally, it is illustrated how the latter result can be used to design a “functional” language which, by means of a disciplined usage of negation, allows to achieve the desired level of expressiveness up to BH so that exponential time resolution is eventually enabled only for hard problems.
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/128003
 Attenzione

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

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