Constrained and rational default logics

Abstract

In this paper we consider constrained and rational default logics We provide two characterizations of constrained extensions One of them is used to derive complexity results for decision problems involving constrained extensions In particular, we show that the problem of membership of a formula in at least one (in all) constrained extension(s) of a default theory is Ef-complete (Ilf-complete) We establish the relationship between constrained and rational default logics We prove that rational ex tensions determine constrained extensions and that for seminormal default theories there is A one-to-one correspondence between these objects We also show that the definition of a constrained extension can be extended to cover the case of default theories which may contain justification-free defaults 1