More procedural is the semiconstructive definition, so called because it suggests a nondeterministic procedure for computing extensions.

Theorem 3.2 (Reiter, 1980) Let         be a set of formulae, and let ∆ =
be a default theory.  Define   o =    and for all      0,   i+1 = Cn(  i)
: 1 n l The set of generating defaults of an extension identifies the extension uniquely, and is of finite size whenever the number of defaults is finite.

Definition 3.3 (Reiter, 1980) Suppose △ =
is a default theory and is an extension of A. The set of generating defaults of with respect to A is

__ GD( A) =  ; and l n
Theorem 3.4 (Reiter, 1980) Suppose - is an extension of a default theory ∆ =
= Cn( GD( 
Then
: 1 The standard consequence relations of default logic are cautious reasoning = c and brave rea so ning = b Definition 3.5 Let ∆ =
be a default theory and a formula. Then ∆ =c if and only if         for all extensions    of ∆ , and ∆ = b    if and only if for some extension    of Δ.

The following terminology is used in referring to default rules of certain syntactic forms.

Defaults of the form :
! 

..

and prerequisite-free . The symbol    denotes a valid formula. Prerequisite-free defaults are often written without prerequisites as : 1 We shall sometimes denote sequences n of justifications by Not all seminormal default theories have extensions, but all ordered default theories do.

In some cases, a decision problem for a class of default theories is intractable, but for the subclass in which the default theories are ordered, it is tractable (Kautz & Selman, 1991).

In later sections we analyze the complexity of decision problems both with and without the orderedness condition.

Definition 3.6 (Etherington, 1987) Let ∆ =          be a seminormal default theory.

Without loss of generality assume that all formulae are in clausal form. The relations «
and « are defined as follows.

1. If $,$ then $=$$1$$\cdots$$n$ for some $1$. For all $i$$j$$1$$n$ such that $i$$\neq$$j$, let $\leq$$j$.  
2. If
, then   =  ; 
forms of , and , respectively.

(a) If i and          , let

$$i{\cimpliedby}\;\;i$$
