## 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.