defined in Lpb and Lsol for each concept name of O and the only logical connective used in Lpb and Lsol is the conjunction ∧. For example, the representation tgt ∈ Lpb of the query mentioned above is:
tgt = chinese ∧ soup ∧ leek ∧ ¬ peanut oil The case base CB contains a set of recipes. Each recipe is indexed in the case base by a propositional formula R ∈ Lsol. For example, the index R of the recipe Wonton Soup is:
R = chinese ∧ soup ∧ green onion ∧ . . . ∧ peanut oil ∧ *Nothing else* Nothing else denotes a conjunction of negative literals ¬ a for all a ∈ V such that chinese ∧ soup ∧ green onion ∧ . . . ∧ peanut oil 2O a. This kind of "closed world assumption" states explicitly that for all propositional variable a ∈ V,
either R O a (the recipe contains the ingredient represented by a) or R O ¬ a
(the recipe does not contain the ingredient represented by a).

Each recipe index R represents a set of source cases: R represents the set of source cases (srce, Sol(srce)) such that Sol(srce) = R and srce is solved by R,
i.e., srce is such that R O srce.

Adaptation Knowledge. In Taaable, adaptation knowledge is given by a set of reformulations (r, Ar) in whichr is a binary relation between problems andAr is an adaptation function associated with r [13]. A reformulation has the following semantics: if two problems pb1 and pb2 are related by r —denoted by pb1 r pb2then for every recipe Sol(pb1) matching the query pb1, Ar(pb1, Sol(pb1), pb2) =
Sol g(pb2) matches the query pb2.

In this paper, binary relations r are given by substitutions of the form σ =
α β, where α and β are literals (either positive or negative). For example, the substitution σ = leek onions generalizes leek into onions.

Adaptation functions Ar are given by substitutions of the form Σ = A B
in which A and B are conjunctions of literals. For example, the substitution Σ = soup ∧ pepper soup ∧ ginger states that pepper can be replaced by ginger in soup recipes. A substitution Σ can be automatically generated from a substitution σ: Σ = b a if σ is of the form a b and Σ = ∅ ¬ a if σ is of the form ¬ a ∅.

The main source of adaptation knowledge is the ontology O. A substitution σ = a b is automatically generated from each axiom a ⇒ b of O and correspond to a *substitution by generalization*. A substitution σ = a b can be applied to a query pb if pb O a. σ generates a new query σ(pb) in which the propositional variable a has been substituted by the propositional variable b. For example, the substitution σ = leek onions is generated automatically from the axiom leek ⇒ onions of O. σ can be applied to the query tgt to produce the query σ(tgt) = chinese ∧ soup ∧ onions ∧ ¬ peanut oil, in which leek has been substituted by onions. For each propositional variable a of V, an additional substitution of the form σ = ¬ a ∅ is generated. Such a substitution can be applied to a problem pb if pb O ¬ a and generates a new problem σ(pb) in which