

![0_image_0.png](0_image_0.png)

the input sentence w1w2    wL is embedded in the program separately as msw(i,d,wd+1)
(0  d  L1) in the second clauses of Rg (this treatment does not aect the complexity argument). q(i,d0,d1) reads that the i-th nonterminal spans from position d0 to position d1, i.e. the substring wd0+1    wd1

. The rst clauses q(i,d0,d2) :- msw(,,), q(j,d0,d1),
q(k,d1,d2) are supposed to be textually ordered according to the lexicographic order for tuples hi; j; k; d0; d2; d1i. As a parser, the top-goal is set to q(1,0,L).

44 It asks the parser to parse the whole sentence w1w2    wL as the syntactic category \1" (sentence).

We make an exhaustive search for this query by OLDT search.45 As before, the multistage depth-rst search strategy and O(1) time access to the solution table are assumed.

Then the time complexity of OLDT search is measured by the number of nodes in the

```
OLDT tree. Let T
           
           (k)
            
           d be the OLDT tree for q(k,d,L). Figure 10 illustrates T
                                                  (1)
                                                   
                                                 d
                                                  for d

```

(0  d  L  3) where msw atoms are omitted. As can be seen, the tree has many similar subtrees, so we put them together (see Note in Figure 10). Due to the depth-rst strategy,

```
T
 
 (1)
  
 d has a recursive structure and contains T
                                 (1)
                                   
                                 d+1 as a subtree. Nodes whose leftmost atom

```

is not underlined are solution nodes, i.e. they solve their leftmost atoms for the rst time in the entire refutation process. The underlined atoms are already computed in the subtrees to their left.46 They only check the solution table if there are their entries (= already
