Comparing Space Efficiency of Propositional Knowledge Representation Formalisms

Marco Cadoli, Francesco M. Donini, Paolo Liberatore, and Marco Schaerf

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},
 }
 
HTTP download.
FTP download.