EXPRESSIVENESS OF STABLE MODEL SEMANTICS FOR DISJUNCTIVE LOGIC PROGRAMS WITH FUNCTIONS

In this paper, we study the expressive power and recursion-theoretic c omplexity of disjunctive logic programs with functions symbols over He rbrand models. In particular, we consider the disjunctive stable model semantics, and show that a relation R is definable over the Herbrand universe of a disjunctive logic program if and only if R is II: defina ble. Thus, disjunctive logic programming under the stable model semant ics expresses exactly II11 and is thus II11 complete over the integers . This result is surprising because it shows that disjunctive logic pr ogramming is not more expressive than normal logic programming under t he stable or well-founded semantics. This sharply contrasts with the f unction-free case. (C) Elsevier Science Inc., 1997.