Lexicographic Ordering as a Basis of Priorities in Default Reasoning

Reference:

Jussi Rintanen. Lexicographic ordering as a basis of priorities in default reasoning. Research Report A41, Helsinki University of Technology, Department of Computer Science and Engineering, Digital Systems Laboratory, Espoo, Finland, December 1996. Doctoral dissertation.

Abstract:

Nonmonotonic reasoning with priorities is investigated. First a version of default logic with priorities is defined. This logic extends Reiter's default logic and uses a priority mechanism that is based on lexicographic comparison. Questions concerning the existence of extensions, monotonicity of default reasoning with respect to priorities, alternative interpretations of partiality in priorities, and computational complexity of prioritized default logic are investigated. An algorithm for automated reasoning in prioritized default logic is presented and proved correct. Two translational inheritance theories are presented. The first is based on normal default theories and the second is based on prerequisite-free normal default theories. Results on the connection between these translational theories and translational theories presented in earlier work are given. Applicability of lexicographic ordering as a basis of priorities for default reasoning in general is discussed.

Keywords:

nonmonotonic logics, default logic, preferences, priorities, lexicographic ordering, computational complexity, inheritance networks

Suggested BibTeX entry:

@techreport{HUT-TCS-A41,
    address = {Espoo, Finland},
    author = {Jussi Rintanen},
    institution = {Helsinki University of Technology, Department of Computer Science and Engineering, Digital Systems Laboratory},
    month = {December},
    note = {Doctoral dissertation},
    number = {A41},
    pages = {vi+187},
    title = {Lexicographic Ordering as a Basis of Priorities in Default Reasoning},
    type = {Research Report},
    year = {1996},
}