Answer Set Programming (ASP) is a well-established formalism for nonmonotonic reasoning. An ASP program can have no answer set due to cyclic default negation. In this case, it is not possible to draw any conclusion, even if this is not intended. Recently, several paracoherent semantics have been proposed that address this issue, and several potential applications for these semantics have been identified. However, paracoherent semantics have essentially been inapplicable in practice, due to the lack of efficient algorithms and implementations. In this paper, this lack is addressed, and several different algorithms to compute semi-stable and semi-equilibrium models are proposed and implemented into an answer set solving framework. An empirical performance comparison among the new algorithms on benchmarks from ASP competitions is given as well.
Many non-monotonic semantics for logic programs with negation have been proposed that can be considered as paracoherent semantics @cite_21 @cite_25 @cite_5 @cite_29 @cite_0 @cite_31 @cite_1 @cite_20 @cite_24 . However, @cite_11 have shown that only semi-stable semantics @cite_32 and semi-equilibrium semantics @cite_11 satisfy the following desiderata properties: (i) every consistent answer set of a program corresponds to a paracoherent answer set (); (ii) if a program has some (consistent) answer set, then its paracoherent answer sets correspond to answer sets (); (iii) if a program has a classical model, then it has a paracoherent answer set (); (iv) a minimal set of atoms should be undefined (); (v) every true atom must be derived from the program ().
@cite_29 @cite_21 @cite_1 @cite_32 @cite_0 @cite_24 @cite_5 @cite_31 @cite_25 @cite_20 @cite_11
2010968193 1565029141 50549667 2085084839
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 extend answer set semantics to deal with inconsistent programs (containing classical negation), by finding a "best" answer set. Within the context of inconsistent programs, it is natural to have a partial order on rules, representing a preference for satisfying certain rules, possibly at the cost of violating less important ones. We show that such a rule order induces a natural order on extended answer sets, the minimal elements of which we call preferred answer sets. We characterize the expressiveness of the resulting semantics and show that it can simulate negation as failure as well as disjunction. We illustrate an application of the approach by considering database repairs, where minimal repairs are shown to correspond to preferred answer sets. In recent years, Answer Set Programming ASP, logic programming under the stable model or answer set semantics, has seen several extensions by generalizing the notion of an atom in these programs: be it aggregate atoms, HEX atoms, generalized quantifiers, or abstract constraints, the idea is to have more complicated satisfaction patterns in the lattice of Herbrand interpretations than traditional, simple atoms. In this paper we refer to any of these constructs as generalized atoms. It is known that programs with generalized atoms that have monotonic or antimonotonic satisfaction patterns do not increase complexity with respect to programs with simple atoms if satisfaction of the generalized atoms can be decided in polynomial time under most semantics. It is also known that generalized atoms that are nonmonotonic being neither monotonic nor antimonotonic can, but need not, increase the complexity by one level in the polynomial hierarchy if non-disjunctive programs under the FLP semantics are considered. In this paper we provide the precise boundary of this complexity gap: programs with convex generalized atom never increase complexity, while allowing a single non-convex generalized atom under reasonable conditions always does. We also discuss several implications of this result in practice. 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 ) .