Comparing Space Efficiency of Propositional Knowledge Representation Formalisms

Proceedings of the Fifth International Conference on the Principles of Knowledge Representation and Reasoning (KR'96)

We investigate the space efficiency of a Propositional Knowledge Representation (PKR) formalism. Informally, the space efficiency of a formalism F in representing a certain piece of knowledge alfa, is the size of the shortest formula of F that represents alfa. In this paper we assume that knowledge is either a set of propositional interpretations or a set of formulae (theorems). We provide a formal way of talking about the relative ability of PKR formalisms to compactly represent a set of models or a set of theorems. We introduce two new compactness measures, the corresponding classes, and show that the relative space efficiency of a PKR formalism in representing models/theorems is directly related to such classes. In particular, we consider formalisms for nonmonotonic reasoning, such as circumscription and default logic, as well as belief revision operators.

 @inproceedings{cado-etal-96-b,
 title = {Comparing Space Efficiency of Propositional Knowledge Representation
 Formalisms},
 year = {1996},
 author = {Cadoli, Marco and Donini, Francesco M. and Liberatore, Paolo and
 Schaerf, Marco},
 booktitle = {Proceedings of the Fifth International Conference on the Principles of
 Knowledge Representation and Reasoning (KR'96)},
 pages = {364-373},
 publisher = {Morgan Kaufmann, Los Altos},
 }