Paracoherent answer set computation

摘要

Answer Set Programming (ASP) is a well-established paradigm for declarative programming and nonmonotonic reasoning. ASP allows for flexible modeling using rules. ASP rules induce a set of intended models called answer sets. Incoherence, the non-existence of answer sets, is therefore a feature of ASP, indicating that the rules admit no intended models. However, this feature can also be problematic in certain circumstances: errors that cause incoherence are notoriously difficult to debug, and query answering will not provide any meaningful answers for incoherent programs. Paracoherent semantics have been suggested as a remedy. They extend the classical notion of answer sets to draw meaningful conclusions also from incoherent programs. 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 within an answer set solving framework. A key role in the framework is played by syntactic program transformations that allow for characterizing paracoherent semantics in terms of the answer sets of transformed programs. Apart from existing transformations from the literature, a novel transformation is also proposed, which provides an alternative characterization of paracoherent semantics in terms of (extended) externally supported models. Notably, the new transformation is more compact than the existing ones, and brings performance benefits. An extensive empirical performance comparison among the algorithms on benchmarks from ASP competitions and a real-world use case is given as well. It shows not only that the methods developed in this paper lead to practically effective systems, but also show a clear advantage of the methods that rely on (extended) externally supported models.