Ordering Default Theories

Chiaki Sakama

Proceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI-03), Morgan Kaufmann Publishers, pages 839-844, 2003.


In first-order logic, a theory T1 is considered stronger than another theory T2 if every formula derived from T2 is also derived from T1. Such an order relation is useful to know relative value between different theories. In the context of default logic, a theory contains default information as well as definite information. To order default theories, it is necessary to assess the information content of a default theory. To this end, we introduce a multi-valued interpretation of default theories based on a nine-valued bilattice. It distinguishes definite and credulous/skeptical default information derived from a theory, and is used for ordering default theories based on their information contents. The technique is also applied to order nonmonotonic logic programs. The results of this paper provide a method for comparing different default theories and have important application to learning nonmonotonic theories.

Full Paper (gzipped postscript 53K) Slide (pdf 421K)