Generality and Equivalence Relations in Default Logic

Katsumi Inoue and Chiaki Sakama

Proceedings of the 22nd Conference on Artificial Intelligence (AAAI-07), pages 434-439, 2007.


Generality or refinement relations between different theories have important applications to generalization in inductive logic programming, refinement of ontologies, and coordination in multi-agent systems. We study generality relations in disjunctive default logic by comparing the amounts of information brought by default theories. Intuitively, a default theory is considered more general than another default theory if the former brings more information than the latter. Using techniques in domain theory, we introduce different types of generality relations over default theories. We show that generality relations based on the Smyth and Hoare orderings reflect orderings on skeptical and credulous consequences, respectively, and that two default theories are equivalent if and only if they are equally general under these orderings. These results naturally extend both generality relations over first-order theories and those for answer set programming.

Full Paper (PDF 141K) , © AAAI Slide (pdf 206K)