Composing extended top-down tree transducers

Proceedings of the 13th Conference of the European Chapter of the Association for Computational Linguistics, pages 808–817, Avignon, France, April 23 - 27 2012. c⃝2012 Association for Computational Linguistics Composing extended top-down tree transducers∗ Aur´elie Lagoutte ´Ecole normale sup´erieure de Cachan, D´epartement Informatique alagoutt@dptinfo.ens-cachan.fr Fabienne Braune and Daniel Quernheim and Andreas Maletti University of Stuttgart, Institute for Natural Language Processing {braunefe,daniel,maletti}@ims.uni-stuttgart.de Abstract A composition procedure for linear and nondeleting extended top-down tree trans- ducers is presented. It is demonstrated that the new procedure is more widely applica- ble than the existing methods. In general, the result of the composition is an extended top-down tree transducer that is no longer linear or nondeleting, but in a number of cases these properties can easily be recov- ered by a post-processing step. 1 Introduction Tree-based translation models such as syn- chronous tree substitution grammars (Eisner, 2003; Shieber, 2004) or multi bottom-up tree transducers (Lilin, 1978; Engelfriet et al., 2009; Maletti, 2010; Maletti, 2011) are used for sev- eral aspects of syntax-based machine transla- tion (Knight and Graehl, 2005). Here we consider the extended top-down tree transducer (XTOP), which was studied in (Arnold and Dauchet, 1982; Knight, 2007; Graehl et al., 2008; Graehl et al., 2009) and implemented in the toolkit TIBURON (May and Knight, 2006; May, 2010). Specifically, we investigate compositions of linear and nondeleting XTOPs (ln-XTOP). Arnold and Dauchet (1982) showed that ln-XTOPs compute a class of transformations that is not closed under composition, so we cannot compose two arbitrary ln-XTOPs into a single ln-XTOP. However, we will show that ln-XTOPs can be composed into a (not necessarily linear or nondeleting) XTOP. To illustrate the use of ln-XTOPs in machine transla- tion, we consider the following English sentence together with a German reference translation: ∗ All authors were financially supported by the EMMY NOETHER project MA / 4959 / 1-1 of the German Research Foundation (DFG). RC PREL that C NP VP �→ C NP VP C NP VP VAUX VPART NP �→ C NP VP VAUX NP VPART Figure 1: Word drop [top] and reordering [bottom]. The newswire reported yesterday that the Serbs have completed the negotiations. Gestern [Yesterday] berichtete [reported] die [the] Nachrichtenagentur [newswire] die [the] Serben [Serbs] h¨atten [would have] die [the] Verhandlungen [negotiations] beendet [completed]. The relation between them can be described (Yamada and Knight, 2001) by three operations: drop of the relative pronoun, movement of the participle to end of the clause, and word-to-word translation. Figure 1 shows the first two oper- ations, and Figure 2 shows ln-XTOP rules per- forming them. Let us now informally describe the execution of an ln-XTOP on the top rule ρ of Figure 2. In general, ln-XTOPs process an in- put tree from the root towards the leaves using a set of rules and states. The state p in the left- hand side of ρ controls the particular operation of Figure 1 [top]. Once the operation has been per- formed, control is passed to states pNP and pVP, which use their …

Content truncated to 500 words