ss one by the insertion of between(D0,D1,D2) is O(NL3) respectively, 51 OLDT time remains O( N 3 L 3 ), and hence so is the size of the support graph.

To apply the graphical EM algorithm correctly, we need to confirm the five conditions on its applicability. It is rather apparent however that the OLDT refutation of any topgoal of the form ~ q'([w1,..,wL]) w.r.t. DBg, terminates, and leaves a support graph st is fying the finite support condition and the acyclic support condition. The t-exclusiveness condition and the independent condition also hold because the refutation process faithfully simulates the leftmost stochastic derivation of w 1 · · w L in which the choice of a production rule made by msw(s;,s~,[s;,sk]) is exclusive and independent (trial-ids are different on different choices).

What remains is the uniqueness condition. To confirm it, let us consider another program DB a ′′ , a modification of DB a ′ such that the first goal length(S,D) in the body of the first clause and the first goal between(DO,D1,D2) in the second clause of R n ′ are moved to the last position in their bodies respectively. DB or and DB or are logically equivalent, and semantically equivalent as well from the viewpoint of distribution semantics. Then think of the sampling execution by the OLDT interpreter of a top-goal ← q'(S) w.r.t. DB a n where S is a variable, using the multi-stage depth-first search strategy. It is easy to see first that the execution never fails, and second that when the OLDT refutation terminates, a sentence
[w1,..., wL] is returned in S, and third that conversely, the set of msw atoms resolved upon in the refutation uniquely determines the output sentence [ w 1 , . . , w L ],52 Hence, if the sampling execution is guaranteed to always terminate, every sampling from PF xx (= PF x )
uniquely generates a sentence, an observable atom, so the uniqueness condition is satisfied by DB n , and hence by DB n .

Then when is the sampling execution guaranteed to always terminate? In other words, when does the grammar only generate finite sentences?  Giving a general answer seems difficult, but it is known that if the parameter values in a PCFG are obtained by learning from finite sentences, the stochastic derivation by the PCFG terminates with probability one (Chi & Geman, 1998). In summary, assuming appropriate parameter values, we can say that the parameterized logic program DB g ′ for the largest PCFG with N nonterminal symbols satisfies all applicability conditions, and the OLDT time for a sentence of length L is O(N 3 L 3 ) 53 and this is also the size of the support graph. From Proposition 5.1, we con clu de Proposition 5.3 Let DB be a parameterized logic program representing a PCFG with N
nnterminals in the form of DB n in Figure 11, and G = G 1 , G 2 , . . . , G T be the sampled atoms representing sentences of length L. We suppose each table operation in OLDT search is done in O(1) time.  Then OLDT search for G and one iteration in learn-gEM are respectively done in O(N³ L³T) time.