IOS Press Well-Founded Semantics for Default Logic

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/Su

Fundamenta Informaticae XX (1997) 1{16 IOS Press

1

Well-Founded Semantics for Default LogicGerhard BrewkaInstitut fur Informatik Universitat Leipzig Augustusplatz 10-11, 04109 Leipzig, Germany brewka@informatik.uni-leipzig.de

Georg Gottlob

Institut fur Informationssysteme Paniglgasse 16, Technical University of Vienna 1040 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 di culty can be solved by varying the xed point operator underlying the semantics. We de ne a range of di erent 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 di er in the e ort 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 de ne prioritized versions of the logics. Keywords: Nonmonotonic reasoning, default logic, well-founded semantics.

1. IntroductionWe investigate in this paper semantics for Reiter's default logic 19] which are based on least xpoints of monotone operators. Such semantics have their roots in logic programming, in particular in well-founded semantics 6, 16, 2], one of the by now standard semantics for logic programs. The success of well-founded semantics in logic programming suggests that its underlying techniques may prove fruitful in other areas of nonmonotonic reasoning as well. The goal of this paper is to answer the question whether these techniques can be generalized in an interesting and useful manner to full default logic.

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/Su

The answer we will give has both a positive and a negative part. It turns out that we can indeed de ne a reasonable semantics for default logic based on least xpoints of adequate monotone operators. This is good news, in particular for those who consider well-founded semantics a genuine semantics of its own determining the right meaning of a logic program, respectively a default theory, in the rst place. On the other hand, our complexity analysis will show that the main reasoning tasks in our well-founded default logics are at least as complex as those in original default

logic, and in an important case even harder. This is bad news, at least for those whose main interest in well-founded semantics stems from the fact that this semantics can be viewed as an approximation of the original semantics, that is, stable model semantics 7] in the case of logic programs and Reiter's semantics in the case of default logic. In logic programming well-founded semantics leads to polynomial algorithms. Our results imply that no corresponding gain in e ciency is to be achieved for full default logic. The idea of extending well-founded semantics to default logic is not new. In fact, two such extensions are described in the literature, namely Baral and Subrahmanian's well-founded semantics for default logic 2] and Przymusinska and Przymusinski's stationary semantics 18]. Both approaches are closely related and agree on the set of skeptical conclusions. In comparison with original default logic they have the following advantages: 1. Since the de nition of the semantics is based on a monotone operator the existence of a least xpoint is guaranteed. Default theories that lack extensions thus have a reasonable consequence relation under the new semantics. 2. The least xpoint can be approximated from below by iterating the monotone operator on the empty set. This gives rise to an iterative procedure for determining default conclusions. 3. The semantics are cumulative, i.e., adding a (skeptical) conclusion to the premises does not change the set of obtainable conclusions. 4. As shown in 10] computing skeptical conclusions for propositional default theories is on the rst level of the polynomial hierarchy and thus more e cient than in Reiter's original approach. Unfortunately, both approaches su er from a serious weakness: it turns out that in many natural situations no defeasible conclusions at all are obtained. In these situations the approaches simply break down to monotonic reasoning from the available facts. This can obviously not be viewed as a satisfactory treatment of default reasoning or, for that matter, as a reasonable generalization of well-founded semantics to default logic. We therefore investigate in this paper alternative generalizations which do not su er from the mentioned problems. Our generalizations have the following two properties in common with Baral/Subrahmanian's and Przymusinska/Przymusinski's approaches: 1. they are based on monotone operator …… 此处隐藏：52431字，全部文档内容请下载后查看。喜欢就下载吧 ……