computed) in O (1) time.  Since all clauses are ground, such execution only generates a single child node.

We enumerate h ( 1 ), the number of nodes in T ( 1 ) but not in T ( k ), ( 1 ≤ k ≤ N ).  From Figure 10, we see h ( 1 ) = O ( N 3 ( L − d ) 2 ) . 47  Let h ( k ) ( 2 ≤ k ≤ N ) be the number of nodes in T d+1 not contained in T d+1 . It is estimated as O(N 2 (L - d - 2)). Consequently, the number of nodes that are newly created in T (1) is h (1) + ∑ ˆ x =2 h (k) = O ( N 3 ( L = d ) 2 ). As a result, total time for OLDT search is computed as ∑ d = 3 h d = O ( N 3 L 3 ) 48 which is also the size of the support graph.

We now consider a non-propositional parsing program DB a , = F a , U R a , in Figure 11 whose ground instances constitute the propositional program DBg. DBg, is a probabilistic variant of DCG program (Pereira & Warren, 1980) in which q'/1, q'/6 and between/3 are declared as table predicate. Semantically DB n ′ specifies a probability distribution over the atoms of the form {q'(l) | lis a list of terminals}.

{msw(si,t,[sj,sk]) | 1 ≤ i,j,k ≤ N,t is a number} Fg l U {msw(si,t,w) | 1 ≤ i ≤ N,t is a number, w is a terminal} q' (S) :-  length(S,D), q'(s1,0,D,0,_,S-[]). q'(I,DO,D2,CO,C2,LO-L2) :- between(DO,D1,D2), mse(I,CO,[J,K]), R,,, q'(J,DO,D1,s(CO),C1,L0-L1), q'(K,D1,D2,s(C1),C2,L1-L2). q'(I,D,s(D),CO,s(CO),[W|X]-X) :- msw(I,CO,W).

## Figure 11: Probabilistic Dcg Like Program Db At

The top-goal to parse a sentence S = [w 1 , . . , w L ] is ← q ′ ([w 1 , . . . , w L ]). It invokes q'(s1,0,D,0,_,[w1,...,wr]-[]) after measuring the length D of an input sentence S by calling length/2. 49 50 In general, q'(i,do,d2,co,c2,lo-l2) works identically to q(i,do,d2)
but three arguments, ∞, c2 and lo-l2 , are added. ∞ supplies a unique trial-id for msws to be used in the body, c2 the latest trial-id in the current computation, and lo-l2 a D-list holding a substring between do and d2 . Since the added arguments do not affect the shape of the