Priorities and Nonmonotonic Reasoning

Reference:

Jussi Rintanen. Priorities and nonmonotonic reasoning. Research Report A28, Helsinki University of Technology, Department of Computer Science and Engineering, Digital Systems Laboratory, Espoo, Finland, December 1993.

Abstract:

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 formalisms to autoepistemic logic. Possible application areas are e.g. default logic, logic programs, deductive databases, and theories of diagnosis. It is shown that prioritized autoepistemic logic is in the propositional case more general than other related formalisms like preferred subtheories of Brewka, structured theories of Ryan, and a propositional version of Lifschitz's prioritized circumscription. Simple polynomial-time translations of these formalisms to prioritized autoepistemic logic are given. Finally, it is demonstrated how automated theorem-proving in prioritized autoepistemic logic benefits from priorities. An algorithm for automated reasoning is given and proved correct.

Keywords:

Nonmonotonic logics, preferences, priorities, automated reasoning

Suggested BibTeX entry:

@techreport{HUT-TCS-A28,
    address = {Espoo, Finland},
    author = {Jussi Rintanen},
    institution = {Helsinki University of Technology, Department of Computer Science and Engineering, Digital Systems Laboratory},
    month = {December},
    number = {A28},
    pages = {90},
    title = {Priorities and Nonmonotonic Reasoning},
    type = {Research Report},
    year = {1993},
}