Tree Parsing for Tree-Adjoining Machine Translation

Matthias Buechse, Heiko Vogler, Mark Jan Nederhof

Research output: Contribution to journalArticlepeer-review


Tree parsing is an important problem in statistical machine translation. In this context, one is given (a) a synchronous grammar that describes the translation from one language into another and (b) a recognizable set of trees; the aim is to construct a finite representation of the set of those derivations that derive elements from the given set, either on the source side (input restriction) or on the target side (output restriction). In tree-adjoining machine translation the grammar is a kind of synchronous tree-adjoining grammar. For this case, only partial solutions to the tree parsing problem have been described, some being restricted to the unweighted case, some to the monolingual case. We introduce a class of synchronous tree-adjoining grammars which is effectively closed under input and output restrictions to weighted regular tree languages, i.e. the restricted translations can again be represented by grammars in the same class; this enables, e.g. cascading restrictions. Moreover, we present an algorithm that constructs these grammars for input and output restriction.
Original languageEnglish
Pages (from-to)351-373
Number of pages23
JournalJournal of Logic and Computation
Issue number2
Publication statusPublished - 2014


Dive into the research topics of 'Tree Parsing for Tree-Adjoining Machine Translation'. Together they form a unique fingerprint.

Cite this