Reductions among KR Formalisms

We now define the forms of reduction between PKR formalisms that we analyze in the following sections. A formula can always be represented as a string over an alphabet , hence from now on we consider translations as functions transforming strings.

Let and be two PKR formalisms. There exists a * poly-size
reduction* from to , denoted as
, if is a
poly-size function such that for any given knowledge base in ,
is a knowledge base in .
Clearly, reductions should be restricted to produce a meaningful output.
In particular, we now discuss
reductions that preserve the models of the original theory.

The semantic approach by Gogic and collegues [21] is that the models of the two knowledge bases must be exactly the same. In other words, if a knowledge base of the formalism is translated into a knowledge base of the formalism , then if and only if . This approach can be summarized by: a reduction between formalisms and is a way to translate knowledge bases of into knowledge bases of , preserving their sets of models. While this semantics is intuitively grounded, it is very easy to show examples in which two formalisms that we consider equally space-efficient cannot be translated to each other. Let us consider for instance a variant of the propositional calculus in which the syntax is that formulas must be of the form , where is a regular formula over the variables . Clearly, this formalism is able to represent knowledge in the same space than the propositional calculus (apart a polynomial factor). However, according to the definition, this formalism cannot be translated to propositional calculus: there is no knowledge base that is equivalent to . Indeed, the only model of is , while any model of any consistent knowledge base of the modified propositional calculus contains .

We propose a more general approach that can deal also with functions
that change the language of the . To this end, we allow for a
translation from models of to models of . We
stress that, to be as general as possible, the translation may depend
on -- i.e., different knowledge bases may have different
translations of their models. We want this translation easy to
compute, since otherwise the computation of could hide the
complexity of reasoning in the formalism. However, observe that to
this end, it is not sufficient to impose that is computable
in polynomial time. In fact, once is fixed, its models could be
trivially translated to models of in constant time, using a
lookup table. This table would be exponentially large, though; and
this is what we want to forbid. Hence, we impose that is a
*circuit* of polynomial-size wrt . We still use a
functional notation to denote the result of applying a
model to the circuit . A formal definition follows.

The rationale of model-preserving reduction is that the knowledge base of the first formalism can be converted into a knowledge base in the second one , and this reduction should be such that each model in can be easily translated into a model in .

We require to depend on , because the transformation , in general, could take the actual form of into account. This happens in the following example of a model-preserving translation.

We reduce a fragment of skeptical default logic [29] to
circumscription with varying letters, using the transformation
introduced by Etherington [15]. Let
be a * prerequisite-free normal* (PFN) default
theory, i.e., all defaults are of the form
, where
is a generic formula. Let be the set of letters
occurring in
. Define as the set of letters
. The function can be
defined in the following way:
,
where
, are the letters to be minimized, and (the set of
letters occurring in
) are varying letters. We show
that is a model-preserving poly-size reduction. In fact, given a
set of PFN defaults let be a function such that for each
interpretation for ,
. Clearly, is poly-size, can be
realized by a circuit whose size is polynomial in , and is a
model of at least one extension of
iff
. The dependence of only on stresses
the fact that, in this case, the circuit does not depend on the
whole knowledge base
, but just on .

Clearly, when models are preserved, theorems are preserved as well. A weaker form of reduction is the following one, where only theorems are preserved. Also in this case we allow theorems of to be translated by a ``simple" circuit to theorems of .

A poly-size reduction
satisfies *
theorem-preservation * if there exists a polynomial such that, for
each knowledge base in , there exists a circuit whose
size is bounded by , and such that for every formula
on the variables of , it holds that
iff
.

The theorem-preserving reduction has a property similar to that of the model-preserving reduction, when the knowledge bases are used to represent theorems rather than models. Namely, a knowledge base is translated into another knowledge base which can be used to represent the same set of theorems. More precisely, we have that each theorem of is represented by a theorem of .

Winslett [50] has shown an example of a reduction from updated knowledge bases to PL that is theorem-preserving but not model-preserving. Using Winslett's reduction, one could use the same machinery for propositional reasoning in the , both before and after the update (plus the reduction). Also the reduction shown in the previous Example 3 is theorem-preserving, this time being the identity circuit.

We remark that our definitions of reduction are more general than those proposed by Gogic and collegues [21]. In fact, these authors consider only a notion analogous to Definition 8. and only for the case when is the identity -- i.e., models in the two formalisms should be identical. By allowing a simple translation between models Definition 8 covers more general forms of reductions preserving models, like the one of Example 3.