Bottom-up computation of perfect models for disjunctive theories

AbstractWe present a new fixpoint characterization of the minimal models of disjunctive logic programs. We prove that by applying the operator iteratively, it characterizes the perfect models semantics of stratified disjunctive logic programs. Given the equivalence between the perfect models semantics of stratified programs and prioritized circumscription, our fixpoint characterization captures the meaning of the corresponding circumscribed theory. Based on these results, we present a bottom-up evaluation algorithm for stratified disjunctive databases. This algorithm uses the model-tree data structure to represent the information contained in the database and to compute answers to queries