On the Expressive Power of Logic Programming Languages with Sets

Abstract

We have compared various ways of introducing sets into logic programming. We have shown that, as long as extra predicates are allowed for intermediate results, quantification is equivalent to having a few primitive, set-theoretic predicates, in the language Furthermore, we have shown that adding negation to ELPS is essentially the same as using LDL grouping clauses Once we require that programs be stratified, most of the languages remain equivalent, but whether ELPS is equivalent to, or strictly more powerful than, LDL remains an open question We also showed that some of the equivalences no longer hold if we do not allow the use of auxiliary predicates. All of our results assume that the sets are finite, and some of the reductions no longer work for infinite sets An interesting question is which of the languages are still equivalent with infinite sets