Paracoherent Answer Set Programming

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 purpose building on a program transformation, called epistemic transformation. We give a model-theoretic characterization of this semantics, considering pairs of two-valued interpretations of the original program, rather than resorting to its epistemic transformation. Moreover, we show some anomalies of semi-stable semantics with respect to basic epistemic properties and propose an alternative semantics satisfying these properties. In addition to a model-theoretic and a transformational characterization of the alternative semantics, we prove precise complexity results for main reasoning tasks under both semantics. (1) Every (consistent) answer set of a program corresponds to a model (answer set coverage). (2) If a (consistent) answer set exists for a program, then all models correspond to an answer set (congruence). (3) If a program has a classical model, then it has a model (classical coherence). Widely-known semantics, such as 3-valued stable models (Przymusinski 1991), L-stable models (Eiter, Leone, and Saccà 1997), revised stable models (Pereira and Pinto 2005), regular models (You and Yuan 1994), and pstable models (Osorio, Ramı́rez, and Carballido 2008), satisfy only part of these requirements (see the Discussion section for further semantics and more details). Semi-stable models (Sakama and Inoue 1995) however, satisfy all three properties and thus are the prevailing paracoherent semantics. Despite the model-theoretic nature of ASP, semi-stable models have been defined by means of a program transformation, called epistemic transformation. A semantic characterization in the style of equilibrium models for answer sets (Pearce and Valverde 2008) is still missing. We address this problem and make the following main contributions.

Authors

• Thomas Eiter
• Michael Fink
• Joao Moura

Keywords

No keywords are indexed for this paper.