assuming the same conditions as inside probability. In view of (16), the problem of computing µ(G t , m) is now reduced to that of computing α(G t , m), which is recursively computable as follows. Suppose A occurs in the ground program DB like

$B_{1}\gets A\wedge W_{1,1},\cdots,B_{1}\gets A\wedge W_{1,i_{1}}$  $B_{K}\gets A\wedge W_{K,1},\cdots,B_{K}\gets A\wedge W_{K,i_{K}}$
As β ( G t ) is a function of β ( B 1 ), . . . , β ( B K ) by our assumption, the chain rule of derivatives leads to

$$\alpha(G_{t},A)=\left(\frac{\partial\beta(G_{t})}{\partial\beta(B_{1})}\right)\left(\frac{\partial\beta(A\wedge W_{1,1})}{\partial\beta(A)}\right)+\cdots+\left(\frac{\partial\beta(G_{t})}{\partial\beta(B_{K})}\right)\left(\frac{\partial\beta(A\wedge W_{K,i_{K}})}{\partial\beta(A)}\right).$$

and hence to 25

$$\begin{array}{r c l}{{\alpha(G_{t},G_{t})}}&{{=}}&{{1}}\\ {{}}&{{}}&{{}}\\ {{\alpha(G_{t},A)}}&{{=}}&{{\alpha(G_{t},B_{1})\sum_{j=1}^{i_{1}}\beta\left(W_{1,j}\right)+\cdots+\alpha(G_{t},B_{K})\sum_{j=1}^{i_{K}}\beta(W_{K,j}).}}\end{array}$$
$$(17)$$
$$(\,1\,8\,)$$

Therefore if all inside probabilities have already been computed, outside probabilities are recursively computed from the top (17) using (18) downward along the program layers. In the case of DB n with f and m being chosen atoms, we compute

$$\left\{\begin{array}{l l}{\alpha\left(\mathbf{f}\,,\mathbf{f}\,\right)}\\ {\alpha\left(\mathbf{f}\,,\mathbf{g}\,\right)}\\ {\alpha\left(\mathbf{f}\,,\mathbf{h}\,\right)}\\ {\alpha\left(\mathbf{f}\,,\mathbf{m}\,\right)}\end{array}\right.$$
$$\begin{array}{r c l}{{\alpha(\mathbf{f},\mathbf{f})}}&{{=}}&{{1}}\\ {{\alpha(\mathbf{f},\mathbf{g})}}&{{=}}&{{\beta\left(\mathbf{a}\right)+\beta(\mathbf{b})}}\\ {{\alpha(\mathbf{f},\mathbf{h})}}&{{=}}&{{\alpha(\mathbf{f},\mathbf{g})\beta(\mathbf{d})}}\\ {{\alpha(\mathbf{f},\mathbf{m})}}&{{=}}&{{\alpha(\mathbf{f},\mathbf{h}).}}\end{array}$$
$$(19)$$

From (19), the desired sum µ (f, m) is calculated as µ(f, m) = α(f, m)β(m) = (β(a) + β(b))β(d)β(m)
which requires only two multiplications and one addition compared to four multiplications and one addition in the naive computation.

Gains obtained by computing inside and outside probability may be small for this case, but as the problem size grows, they become enormous, and compensate enough for additional restrictions imposed on the result of OLDT search.

## 4.7 Oldt Search

To compute inside and outside probability recursively like (15) or (17) and (18), we need at programming level a tabulation mechanism for structure-sharing of partial explanations 2. Because of the independence assumption on body atoms, Wh,j (1 < h < K, 1 < j < in ) and A are AA
∂β ( A )β ( W n, j ) = β ( W n, j )
AB
∂β ( A )