More formally, F represents the set of models A**, because for each interpretation** I, I ∈ A
holds if and only if I |= F. The formula F also represents the set of formulae C**, because**
Cn(F) = Cn(C), where Cn(.) **is the function that gives the set of all conclusions that can**
be drawn from a propositional formula.

## 1.1 State Of The Art

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 (1991, 1994)
proposed a translation from default logic to PL, and a translation from disjunctive logic programs to PL, while Winslett (1989) introduced a translation from revised knowledge bases to PL, and Gelfond, Przymusinska, and Przymusinskyi (1989) 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 (1996) have shown that many interesting fragments of default logic and circumscription cannot be expressed by polynomialtime 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 (Cadoli, Donini, Schaerf, & Silvestri, 1997) and most operators for belief revision into PL (Cadoli, Donini, **Liberatore, & Schaerf, 1999;**
Liberatore, 1995).

Gogic and collegues (1995) 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 (1995) and Khardon and Roth (1996, **1997) 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 (Cadoli, Donini, Liberatore, & Schaerf, 1996b), a new complexity measure for decision problems, called compilability**, has been introduced. In the**