PARSING N ON-IM M EDIATE D O M INANCE RELATIONS

We present a new technique for parsing grammar formalisms that express non-immediate dominance relations by 'dominance-links'. Dominance links have been introduced in various formalisms such as extensions to CFG and TAG in order to capture long-distance dependencies in free-word order languages ( Becker et al. , 1 99 1 ; Rambow, 1 994). We show how the addition of 'link counters' to standard parsing algorithms such as CKY- and Earleybased methods for TAG results in a polynomial time complexity algorithm for parsing lexicalized VTAG, a multi-component version of TAGs defined in (Rambow, 1 994) . A variant of this method has previously been applied to context-free grammar based formalisms such as UVG-DL.