Paracoherent Answer Set Programming
Thomas Eiter, Michael Fink, João Moura · 2010
We study the problem of reasoning from incoherent answer set programs, i.e., from logic programs that do not have an answer set due to cyclic dependencies of an atom from its default negation. As a starting point we consider so-called semi-stable models which have been developed for this pur-pose building on a program transformation, called epistemic transformation. We give a model-theoretic characterization of this semantics, considering pairs of two-valued interpreta-tions of the original program, rather than resorting to its epis-temic transformation. Moreover, we show some anomalies of semi-stable semantics with respect to basic epistemic prop-erties and propose an alternative semantics satisfying these properties. In addition to a model-theoretic and a transforma-tional characterization of the alternative semantics, we prove precise complexity results for main reasoning tasks under both semantics.