Gelfond and Zhang recently proposed a new stable model semantics based on Vicious Circle Principle in order to improve the interpretation of logic programs with aggregates. The paper focuses on this proposal, and analyzes the complexity of both coherence testing and cautious reasoning under the new semantics. Some surprising results highlight similarities and differences versus mainstream stable model semantics for aggregates. Moreover, the paper reports on the design of compilation techniques for implementing the new semantics on top of existing ASP solvers, which eventually lead to realize a prototype system that allows for experimenting with Gelfond-Zhang's aggregates. To appear in Theory and Practice of Logic Programming (TPLP), Proceedings of ICLP 2015.
Other relevant stable model semantics for logic programs with aggregates are reported in @cite_3 @cite_9 for disjunction-free programs, recently extended to the disjunctive case in @cite_24 . In these semantics the stability check is not given in terms of minimality of the model for the program reduct but obtained by means of a fixpoint operator similar to immediate consequence, and the following relation holds in general: stable models of @cite_24 are a selection of F-stable models, and they coincide up to ASP( @math ,M,C), which is also the complexity boundary between the first and second level of the polynomial hierarchy for F-stable model semantics @cite_17 . Finally, a more recent proposal is G-stable model semantics @cite_8 , whose relation with other semantics has been highlighted by @cite_20 in the disjunction-free case: G-stable models are F-stable models, but the converse is not always true.
@cite_8 @cite_9 @cite_3 @cite_24 @cite_20 @cite_17
49730540 2085084839 2010968193 1520574003
Recently Ferraris, Lee and Lifschitz proposed a new definition of stable models that does not refer to grounding, which applies to the syntax of arbitrary first-order sentences. We show its relation to the idea of loop formulas with variables by Chen, Lin, Wang and Zhang, and generalize their loop formulas to disjunctive programs and to arbitrary first-order sentences. We also extend the syntax of logic programs to allow explicit quantifiers, and define its semantics as a subclass of the new language of stable models by Such programs inherit from the general language the ability to handle nonmonotonic reasoning under the stable model semantics even in the absence of the unique name and the domain closure assumptions, while yielding more succinct loop formulas than the general language due to the restricted syntax. We also show certain syntactic conditions under which query answering for an extended program can be reduced to entailment checking in first-order logic, providing a way to apply first-order theorem provers to reasoning about non-Herbrand stable models. We introduce the stable model semantics fordisjunctive logic programs and deductive databases, which generalizes the stable model semantics, defined earlier for normal (i.e., non-disjunctive) programs. Depending on whether only total (2-valued) or all partial (3-valued) models are used we obtain thedisjunctive stable semantics or thepartial disjunctive stable semantics, respectively. The proposed semantics are shown to have the following properties: • For normal programs, the disjunctive (respectively, partial disjunctive) stable semantics coincides with thestable (respectively,partial stable) semantics. • For normal programs, the partial disjunctive stable semantics also coincides with thewell-founded semantics. • For locally stratified disjunctive programs both (total and partial) disjunctive stable semantics coincide with theperfect model semantics. • The partial disjunctive stable semantics can be generalized to the class ofall disjunctive logic programs. • Both (total and partial) disjunctive stable semantics can be naturally extended to a broader class of disjunctive programs that permit the use ofclassical negation. • After translation of the programP into a suitable autoepistemic theory ( P ) the disjunctive (respectively, partial disjunctive) stable semantics ofP coincides with the autoepistemic (respectively, 3-valued autoepistemic) semantics of ( P ) . Let P be an arbitrary theory and let X be any given logic. Let M be a set of atoms. We say that M is a X-stable model of P if M is a classical model of P and P∪¬M proves in logic X all atoms in M, this is denoted by P∪¬M ⊩xM. We prove that being an X-stable model is an invariant property for disjunctive programmes under a large class of logics. Two kinds of logics are mainly considered: paraconsistent logics and normal modal logics. For modal logics we use a translation proposed by Gelfond that replaces ¬a with ¬□a. As a consequence we prove that several semantics (recently introduced) for non-monotonic reasoning are equivalent for disjunctive programmes. In addition, we show that such semantics can be characterized by a fixed-point operator in terms of classical logic. We also present a simple translation of a disjunctive programme D into a normal programme N, such that the PStable model semantics of N corresponds to the stable semantics of D over the common language. We present the formal proof of this statement. We introduce a family of partial stable model semantics for logic programs with arbitrary aggregate relations. The semantics are parametrized by the interpretation of aggregate relations in three-valued logic. Any semantics in this family satisfies two important properties: (i) it extends the partial stable semantics for normal logic programs and (ii) total stable models are always minimal. We also give a specific instance of the semantics and show that it has several attractive features.