© 2000 AI Access Foundation and Morgan Kaufmann Publishers. All rights reserved.

**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

We investigate the * space efficiency* of a Propositional
Knowledge Representation (PKR) formalism. Intuitively, the space
efficiency of a formalism in representing a certain piece of
knowledge , is the size of the shortest formula of that
represents . 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.

- Introduction
- Notations and Assumptions
- Compilability Classes
- Reductions among KR Formalisms
- Comparing the Space Efficiency of PKR Formalisms
- Applications
- Related Work and Conclusions
- Bibliography
- About this document ...