A question that has been deeply investigated, and is related to space efficiency, is the possibility of translating a formula expressed in one formalism into a formula expressed in another formalism (under the assumption, of course, that these formulae represent the same knowledge).
In most cases, the analysis is about the possibility of translating formulae from different formalisms to Propositional Logic (PL). For example, Ben-Eliyahu and Dechter [1,2] proposed a translation from default logic to PL, and a translation from disjunctive logic programs to PL, while Winslett [50] introduced a translation from revised knowledge bases to PL, and Gelfond, Przymusinska, and Przymusinskyi [19] defined a translation from circumscription to PL.
All the above translations, as well as many other ones in the literature, lead to an exponential increase of the size of the formula, in the worst case. When the best known translation yields a formula in the target formalism which has exponential size w.r.t. the formula in the source formalism, a natural question arising is whether such exponential blow up is due to the specific translation, or is intrinsic of the problem. For example, although all proposed translations from default logic to PL lead to the exponential blow up, we cannot conclude that all possible translations suffer from this problem: it could be that a polynomial translation exists, but it has not discovered so far.
Some works have focussed on the question of whether this kind of exponential increase in the size is intrinsic or not. Cadoli, Donini, and Schaerf [10] have shown that many interesting fragments of default logic and circumscription cannot be expressed by polynomial-time fragments of PL without super-polynomially increasing the size of formulae. It has been proved that such a super-polynomial increase of size is necessary when translating unrestricted propositional circumscription [11] and most operators for belief revision into PL [8,35].
Gogic and collegues [21] analyzed the relative succinctness of several PKR formalisms in representing sets of models. Among other results, they showed that skeptical default logic can represent sets of models more succinctly than circumscription.
Kautz, Kearns, and Selman [28] and Khardon and Roth [31,32] considered representations of knowledge bases based on the notion of characteristic model, comparing them to other representations, e.g., based on clauses. They showed that the representation of knowledge bases with their characteristic models is sometimes exponentially more compact than other ones, and that the converse is true in other cases.
However, all the above results are based on specific proofs, tailored to a specific reduction, and do not help us to define equivalence classes for the space efficiency of KR formalisms. In a recent paper [6], a new complexity measure for decision problems, called compilability, has been introduced. In the present paper we show how this new measure can be directly used to characterize the space efficiency of PKR formalisms. We emphasize methodological aspects, expressing in a more general context many of the results presented before.