Non-Monotonic Systems: A Framework for Analyzing Semantics and Structural Properties of NMR

Reference:

Tomi Janhunen. Non-monotonic systems: A framework for analyzing semantics and structural properties of NMR. Research Report A49, Helsinki University of Technology, Department of Computer Science and Engineering, Digital Systems Laboratory, Espoo, Finland, March 1998. Doctoral dissertation.

Abstract:

Non-monotonic systems are introduced as a framework for analyzing non-monotonic reasoning. Such systems are defined as parametrized inference operators in a way that is compatible with Tarski's characterization of classical reasoning. The generality of the framework is demonstrated by presenting non-monotonic systems for the leading non-monotonic logics such as circumscription, default logic and autoepistemic logic.

Various translations between non-monotonic logics are studied within the framework. Non-monotonic systems associated with the non-monotonic logics under consideration are shown to be preserved by these translations - including new translations between default logic and bimodal autoepistemic logic presented in the work.

The standard semantics of non-monotonic reasoning - stable and stationary semantics - are generalized for all non-monotonic systems. Various properties of the semantics such as cumulativity and computational complexity are addressed. Moreover, it is established that the translation functions presented preserve these semantics.

Finally, a new semantics called cautious semantics is obtained as a systematic refinement of stationary semantics. Cautious semantics is analyzed using the methodology developed in the work. A comparison is made with similar approaches in the literature. Applications of cautious semantics are considered in the fields of logic programming and consistency-based diagnosis.

Keywords:

non-monotonic reasoning, semantics, cumulativity, computational complexity

Suggested BibTeX entry:

@techreport{HUT-TCS-A49,
    address = {Espoo, Finland},
    author = {Tomi Janhunen},
    institution = {Helsinki University of Technology, Department of Computer Science and Engineering, Digital Systems Laboratory},
    month = {March},
    note = {Doctoral dissertation},
    number = {A49},
    pages = {211},
    title = {Non-Monotonic Systems: A Framework for Analyzing Semantics and Structural Properties of {NMR}},
    type = {Research Report},
    year = {1998},
}