Well-Founded Semantics for Default Logic

Article type: Research Article

Authors: Brewka, Gerhard | Gottlob, Georg

Affiliations: Institut für Informatik, Universität Leipzig, Augustusplatz 10-11, 04109 Leipzig, Germany. brewka@informatik.uni-leipzig.de | Institut für Informationssysteme, Paniglgasse 16, Technical University of Vienna, l040 Vienna, Austria. gottlob@dbai.tuwien.ac.at

Abstract: Default logic is one of the most popular approaches to model defeasible reasoning. Nevertheless, there are a number of problems with Reiter's original semantics that have led to the investigation of alternative approaches. In particular, Baral/Subrahmanian and Przymusinska/Przymusinski have investigated generalizations of well-founded semantics for normal logic programs to default logic. These generalizations have a number of interesting properties. Unfortunately, it turns out that in many realistic situations they are unable to draw any defeasible conclusions at all - which can hardly be viewed as satisfactory. We show how this difficulty can be solved by varying the fixed point operator underlying the semantics. We define a range of different semantics. All of them are correct wrt. safe conclusions under Reiter semantics, i.e. those conclusions with the same proof in all extensions. For the strongest semantics we have also completeness in the case of coherent default theories, i.e. default theories with at least one extension. The logics differ in the effort spent for determining potential conclusions. It turns out that they are at least as complex as original default logic. We show that our approach also leads to new semantics for normal and extended logic programs. Moreover, we define prioritized versions of the logics.

Keywords: Nonmonotonic reasoning, default logic, well-founded semantics

DOI: 10.3233/FI-1997-313402

Journal: Fundamenta Informaticae, vol. 31, no. 3-4, pp. 221-236, 1997