first-order language is used, more results on compactness and existence of reductions are reported by Schlipf (1995).

Khardon and Roth (1996, 1997), and Kautz, Kearns and Selman (1995) propose modelbased representations of a KB **in Propositional Logic, and compare it with formula-based**
representations. Although their results are significant for comparing representations within PL, they refer only to this formalism, hence they are not applicable to our comparison between different **PKR formalisms. The same comment applies also to the idea of representing**
a KB **with an efficient basis by Moses and Tennenholz (1996), since it refers only to one** PKR formalism, namely, PL.

An active area of research studies the connections of the various non-monotonic logics.

In particular, there are several papers discussing the existence of translations that are polynomial in time and satisfy other intuitive requirements such as modularity and **faithfulness**.

Janhunen (1998), improving on results of Imielinski (1987) **and Gottlob (1995), shows that** default logic is the most expressive, among the non-monotonic logics examined, since both circumscription and autoepistemic logic can be modularly and faithfully embedded in default logic, but not the other way around. While these results are of interest and help to fully understand the relation among many knowledge representation formalisms, they are not directly related to ours. In fact, we allow for translations that are more general than polynomial time, while in all of the above papers they only consider translations that use polynomial time and also satisfy additional requirements.

The first result on compactness of representations for a propositional language is presented, to the best of our knowledge, by Kautz and Selman (1992). They show that, unless there is a collapse in the polynomial hierarchy, the size of the smallest representation of the least Horn upper bound of a propositional theory is superpolynomial in the size of the original theory. These results are also presented in a different form in the more comprehensive paper (Selman & Kautz, 1996). The technique used in the proof has been then used by us and other researchers to prove several other results on the relative complexity of propositional knowledge representation formalisms (Cadoli et al., 1996, 1997, 1999; Gogic et al., 1995).

In a recent paper (Cadoli et al., 1996b) we introduced a new complexity measure, i.e.,
compilability**. In this paper we have shown how this measure is inherently related to the**
succinctness of PKR formalisms. We analyzed PKR formalisms with respect to two succinctness measures: succinctness in representing sets of models **and succinctness in representing**
sets of theorems.

The main advantage of our framework is the machinery necessary for a formal way of talking about the relative ability of PKR formalisms to compactly represent information. In particular, we were able to formalize the intuition that a specific PKR formalism provides "one of the most compact ways to represent models/theorems" **among the PKR formalisms** of a specific class.

In our opinion, the proposed framework improves over the state of the art in two different aspects:
1. All the proofs presented in the previous papers only compare pairs of PKR formalisms, for example propositional circumscription and Propositional Logic (Cadoli et al., 1997). These results do not allow for a precise classification of the level of