We investigate the expressive power of patial model semantics for disjunctive deductive databases. In particular, partial stable, regular model, maximal stable, and least underfined stable semantics for function-free disjunctive logic programs are comsidered, for which the expressiveness of queries based on possibility and certainty inference is determined. The analysis pays particular attenion to the impact ofsyntactical restrictions on programs in the form of limited use of disjunction and negation. IT appears that the considered semantics capture complexity classes at the lower end of the polynomial hierarchy. In particular, L-stable semantics has the highest expressive power(sum_3~P resp. II_3~P). An Interesting result in this course is that, in contrast with total stable models, negation is for partial stable models more expressive than disjunction.
展开▼
