Next: Comparing the Space Efficiency Up: Space Efficiency of Propositional Previous: Compilability Classes

# 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.

Definition 8 (Model Preservation)   A poly-size reduction satisfies model-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 interpretation of the variables of it holds that iff .

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.

Example 3

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 .

Definition 9 (Theorem Preservation)

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.

Next: Comparing the Space Efficiency Up: Space Efficiency of Propositional Previous: Compilability Classes
Paolo Liberatore
2000-07-28