The idea of comparing the compactness of KR formalisms in representing information is not novel in AI. It is well known that first-order circumscription can be represented in second-order logic . Kolaitis and Papadimitriou  discuss several computational aspects of circumscription. Among many interesting results they show a reduction from a restricted form of first-order circumscription into first-order logic. The proposed reduction will increase the size of the original formula by an exponential factor. It is left as an open problem to show whether this increase is intrinsic, because of the different compactness properties of the two formalisms, or there exists a more space-efficient reduction. When a first-order language is used, more results on compactness and existence of reductions are reported by Schlipf .
Khardon and Roth [31,32], and Kautz, Kearns and Selman  propose model-based representations of a 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 with an efficient basis by Moses and Tennenholz , 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 , improving on results of Imielinski  and Gottlob , 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 . 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 . 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 [10,11,8,21].
In a recent paper  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: