We call this subset the class of autoepistemic programs . Every autoepistemic program T can be translated into a knowledge base by representing the formula ae as the knowledge base rule cl . Thus, algorithms for computing stable models may be used in computing expansions of autoepistemic programs. Note the appearance of E in the condition. Now consider the subset of default theories that we call default programs .
E is an extension of iff E is a stable model of .
Algorithms for computing stable models can thus be used in computing extensions of Reiter s default theories. The paper is organized as follows. In the next section, we define our terminology. Section 3 presents two algorithms for computing all stable models of a knowledge base. The complexity of the first of these algorithms depends on the number of atoms appearing negatively in the knowledge base, while the complexity of the other algorithm depends on the number of rules having negative atoms in their bodies.