Journal of Artificial Intelligence Research 13 (2000), pp. 1-31. Submitted 8/99; published 8/00.
© 2000 AI Access Foundation and Morgan Kaufmann Publishers. All rights reserved.

Space Efficiency of Propositional Knowledge Representation Formalisms

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

Marco Cadoli
Dipartimento di Informatica e Sistemistica
Università di Roma ``La Sapienza''
Via Salaria 113, I-00198, Roma, Italy
cadoli@dis.uniroma1.it

Francesco M. Donini
Politecnico di Bari
Dipartimento di di Elettrotecnica ed Elettronica
Via Orabona 4, I-70125, Bari, Italy
donini@dis.uniroma1.it

Paolo Liberatore
Dipartimento di Informatica e Sistemistica
Università di Roma ``La Sapienza''
Via Salaria 113, I-00198, Roma, Italy
liberato@dis.uniroma1.it

Marco Schaerf
Dipartimento di Informatica e Sistemistica
Università di Roma ``La Sapienza''
Via Salaria 113, I-00198, Roma, Italy
schaerf@dis.uniroma1.it

Abstract:

We investigate the space efficiency of a Propositional Knowledge Representation (PKR) formalism. Intuitively, the space efficiency of a formalism $F$ in representing a certain piece of knowledge $\alpha$, is the size of the shortest formula of $F$ that represents $\alpha$. In this paper we assume that knowledge is either a set of propositional interpretations (models) or a set of propositional 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 and the stable model semantics for logic programs with negation. One interesting result is that formalisms with the same time complexity do not necessarily belong to the same space efficiency class.