Priorities and Nonmonotonic Reasoning

Many knowledge-based systems use some kind of priorities for controlling their reasoning. In this work, autoepistemic logic is extended with priorities. Priorities are formalized as partial orders of formulae that express that some formulae are preferred to others. Priorities increase the set of conclusions that can be inferred from a set of formulae, because the number of cases where conflicts between defaults are left unresolved decreases. A decision procedure for prioritized autoepistemic logic is given in terms of a decision procedure for a classical logic on which the prioritized autoepistemic logic is based. The complexity of the logic is analyzed with respect to the underlying classical logic. When the classical logic is the propositional logic, the decision problems of prioritized autoepistemic logic are located on the third level of the polynomial hierarchy. The results of this work carry to other formalisms as well because of the existence of translations of other formalism..