Lifschitz introduced the notion of defining extensions of predicate default theories not as absolute, but relative to a specified domain. We look specifically at default theories over a countable domain and show the set of default theories which possess an ω -extension is Σ 2 1 -complete. That the set is in Σ 2 1 is shown by writing a nearly circumscriptive formula whose ω -models correspond to the ω -extensions of a given default theory; similarly, Σ 2 1 -hardness (...) is established by a method for translating formulas into default theories in such a way that ω -models of the circumscriptive formula correspond to ω -extensions of the default theory. (shrink)

When reasoning about complex domains, where information available is usually only partial, nonmonotonic reasoning can be an important tool. One of the formalisms introduced in this area is Reiter's Default Logic (1980). A characteristic of this formalism is that the applicability of default (inference) rules can only be verified in the future of the reasoning process. We describe an interpretation of default logic in temporal epistemic logic which makes this characteristic explicit. It is shown that this interpretation yields a semantics (...) for default logic based on temporal epistemic models. A comparison between the various semantics for default logic will show the differences and similarities of these approaches and ours. (shrink)