A Tree Transducer Model for Synchronous Tree-Adjoining Grammars

Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics, pages 1067–1076, Uppsala, Sweden, 11-16 July 2010. c⃝2010 Association for Computational Linguistics A Tree Transducer Model for Synchronous Tree-Adjoining Grammars Andreas Maletti Universitat Rovira i Virgili Avinguda de Catalunya 25, 43002 Tarragona, Spain. andreas.maletti@urv.cat Abstract A characterization of the expressive power of synchronous tree-adjoining grammars (STAGs) in terms of tree transducers (or equivalently, synchronous tree substitution grammars) is developed. Essentially, a STAG corresponds to an extended tree transducer that uses explicit substitution in both the input and output. This characteri- zation allows the easy integration of STAG into toolkits for extended tree transducers. Moreover, the applicability of the charac- terization to several representational and algorithmic problems is demonstrated. 1 Introduction Machine translation has seen a multitude of for- mal translation models. Here we focus on syntax- based (or tree-based) models. One of the old- est models is the synchronous context-free gram- mar (Aho and Ullman, 1972). It is clearly too weak as a syntax-based model, but found use in the string-based setting. Top-down tree transduc- ers (Rounds, 1970; Thatcher, 1970) have been heavily investigated in the formal language com- munity (G´ecseg and Steinby, 1984; G´ecseg and Steinby, 1997), but as argued by Shieber (2004) they are still too weak for syntax-based machine translation. Instead Shieber (2004) proposes syn- chronous tree substitution grammars (STSGs) and develops an equivalent bimorphism (Arnold and Dauchet, 1982) characterization. This character- ization eventually led to the rediscovery of ex- tended tree transducers (Graehl and Knight, 2004; Knight and Graehl, 2005; Graehl et al., 2008), which are essentially as powerful as STSG. They had been studied already by Arnold and Dauchet (1982) in the form of bimorphisms, but received little attention until rediscovered. Shieber (2007) claims that even STSGs might be too simple to capture naturally occuring transla- tion phenomena. Instead Shieber (2007) suggests a yet more powerful mechanism, synchronous tree-adjoining grammars (STAGs) as introduced by Shieber and Schabes (1990), that can capture certain (mildly) context-sensitive features of natu- ral language. In the tradition of Shieber (2004), a characterization of the power of STAGs in terms of bimorphims was developed by Shieber (2006). The bimorphisms used are rather unconventional because they consist of a regular tree language and two embedded tree transducers (instead of two tree homomorphisms). Such embedded tree transduc- ers (Shieber, 2006) are particular macro tree trans- ducers (Courcelle and Franchi-Zannettacci, 1982; Engelfriet and Vogler, 1985). In this contribution, we try to unify the pic- ture even further. We will develop a tree trans- ducer model that can simulate STAGs. It turns out that the adjunction operation of an STAG can be explained easily by explicit substitution. In this sense, the slogan that an STAG is an STSG with adjunction, which refers to the syntax, also trans- lates to the semantics. We prove that any tree transformation computed by an STAG can also be computed by an STSG using explicit substitution. Thus, a simple evaluation procedure that performs the explicit substitution is all …

Content truncated to 500 words