Transforming Dependency Structures to LTAG Derivation Trees

Caio Corro (1) , Joseph Le Roux (2, 2)

1 ILLC - Institute for Logic, Language and Computation
2 LIPN - Laboratoire d'Informatique de Paris-Nord

We propose a new algorithm for parsing Lexicalized Tree Adjoining Grammars (LTAGs) which uses pre-assigned bilexi-cal dependency relations as a filter. That is, given a sentence and its corresponding well-formed dependency structure, the parser assigns elementary trees to words of the sentence and return attachment sites compatible with these elementary trees and predefined dependencies. Moreover, we prove that this algorithm has a linear-time complexity in the input length. This algorithm returns all compatible derivation trees as a packed forest. This result is of practical interest to the development of efficient weighted LTAG parsers based on derivation tree decoding.

Domaines: Informatique et langage [cs.CL]

Caio Corro, Joseph Le Roux. Transforming Dependency Structures to LTAG Derivation Trees. 13th International Workshop on Tree Adjoining Grammars and Related Formalisms (TAG+13), Sep 2017, Umea, Sweden. pp.112-121. ⟨hal-01988871⟩