Google Code-in

This paper describes how to create word-order domains from a dependency tree. Implement an algorithm to produce word-order domains.

Creating word order domains.

In the first step, we build the word order domains d_h for all nodes h ∈ y of a dependency tree y. A domain is defined as a node and all of its direct dependents. For example, the tree shown in Figure 3 has the following domains:

{it, be, should}, {what, support, should, try}, {federal, support}, {try, to}, {to, achieve}

If an edge was lifted before the linearisation, the lifted node will end up in the word order domain of its new head rather than in the domain of its original head. This way, the lineariser can deduce word orders that would result in non-projective structures in the non-lifted tree