Rational default logic and its applications to logic programming

This dissertation describes a nonmonotonic formalism called rational default logic, which is a modification of Reiter's default logic. The default logic of Reiter has many desirable properties. However, there are situations where this formalism is not easily applicable. Reiter's default logic does not handle incomplete information, given in the form of disjunctive clauses, well. To remedy this problem several modifications of default logic were proposed. We investigate one such modification. In standard default logic the consistency of every justification with a given context is considered separately. The key feature of our formalism is the requirement that all the justifications of defaults used in reasoning must be jointly consistent with a given context. In particular, defaults with mutually inconsistent justifications cannot be used in the construction of the same belief set (extension). We define and study several types of belief sets that can be associated with a default theory: rational extensions, skeptical rational extensions, superrational extensions, weak rational extensions, and weak superrational extensions. These structures correspond to various modes of default reasoning from a default theory. We discuss general properties of these structures and study special cases of normal and seminormal default theories and default translations of logic programs. We show that every seminormal default theory has a rational extension, a skeptical rational extension, and a superrational extension. For normal default theories and default translations of logic programs extensions coincide with both rational and superrational extensions. Rational extensions can be used to define new semantics for logic programming. Moreover, we propose algorithms for computing the structures in question and we present complexity results for reasoning with these structures. We also study connections between rational and constrained default logic. Semi-representability results for rational default logic are also presented. Finally, we address the issue of implementing the proposed algorithms.