Comparing space efficiency of propositional knowledge representation formalisms
Marco Cadoli, Francesco M. Donini, Paolo Liberatore, Marco Schaerf · 1996
. We investigate the space eciency of a Propositional Knowledge Representation (PKR) formalism. Informally, the space eciency of a formalism F in representing a certain piece of knowledge , is the size of the shortest formula of F that represents . 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 eciency 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. 1 Introduction Motivations. During the last years a large number of formalisms for knowledge representation (KR) have been prop...