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.
Scheda prodotto non validato
Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo
|Titolo:||"Possible is Certain" is Desiderable and can be Expressive|
|Data di pubblicazione:||1997|
|Citazione:||"Possible is Certain" is Desiderable and can be Expressive / Greco, Sergio; Saccà, D.. - In: ANNALS OF MATHEMATICS AND OF ARTIFICIAL INTELLIGENCE. - ISSN 1012-2443. - 10(1-2)(1997), pp. 147-168.|
|Appare nelle tipologie:||1.1 Articolo in rivista|