POSSIBLE IS CERTAIN IS DESIRABLE AND CAN BE EXPRESSIVE

The partial stable models of a logic program form a class of models th at include the (unique) well-founded model, total stable models and ot her two interesting subclasses: maximal stable models and least undefi ned stable models. As stable models different from the well-founded ar e not unique, DATALOG queries do not in general correspond to function s. The question is: what are the expressive powers of the various type s of stable models when they are restricted to the class of all functi onal queries? The paper shows that this power does not go in practice beyond the one of stratified queries, except for least undefined stabl e models which, instead, capture the whole Boolean hierarchy BH. Final ly, it is illustrated how the latter result can be used to design a '' functional'' language which, by means of a disciplined usage of negati on, allows to achieve the desired level of expressiveness up to BH so that exponential time resolution is eventually enabled only for hard p roblems.