Optimal k-arization of Synchronous Tree-Adjoining Grammar

Proceedings of ACL-08: HLT, pages 604–612, Columbus, Ohio, USA, June 2008. c⃝2008 Association for Computational Linguistics Optimal k-arization of Synchronous Tree-Adjoining Grammar Rebecca Nesson School of Engineering and Applied Sciences Harvard University Cambridge, MA 02138 nesson@seas.harvard.edu Giorgio Satta Department of Information Engineering University of Padua I-35131 Padova, Italy satta@dei.unipd.it Stuart M. Shieber School of Engineering and Applied Sciences Harvard University Cambridge, MA 02138 shieber@seas.harvard.edu Abstract Synchronous Tree-Adjoining Grammar (STAG) is a promising formalism for syntax- aware machine translation and simultaneous computation of natural-language syntax and semantics. Current research in both of these areas is actively pursuing its incorporation. However, STAG parsing is known to be NP-hard due to the potential for intertwined correspondences between the linked nonter- minal symbols in the elementary structures. Given a particular grammar, the polynomial degree of efficient STAG parsing algorithms depends directly on the rank of the grammar: the maximum number of correspondences that appear within a single elementary structure. In this paper we present a compile-time algorithm for transforming a STAG into a strongly-equivalent STAG that optimally minimizes the rank, k, across the grammar. The algorithm performs in O(|G| + |Y | · L3 G) time where LG is the maximum number of links in any single synchronous tree pair in the grammar and Y is the set of synchronous tree pairs of G. 1 Introduction Tree-adjoining grammar is a widely used formal- ism in natural-language processing due to its mildly- context-sensitive expressivity, its ability to naturally capture natural-language argument substitution (via its substitution operation) and optional modifica- tion (via its adjunction operation), and the existence of efficient algorithms for processing it. Recently, the desire to incorporate syntax-awareness into ma- chine translation systems has generated interest in the application of synchronous tree-adjoining gram- mar (STAG) to this problem (Nesson, Shieber, and Rush, 2006; Chiang and Rambow, 2006). In a par- allel development, interest in incorporating seman- tic computation into the TAG framework has led to the use of STAG for this purpose (Nesson and Shieber, 2007; Han, 2006b; Han, 2006a; Nesson and Shieber, 2006). Although STAG does not in- crease the expressivity of the underlying formalisms (Shieber, 1994), STAG parsing is known to be NP- hard due to the potential for intertwined correspon- dences between the linked nonterminal symbols in the elementary structures (Satta, 1992; Weir, 1988). Without efficient algorithms for processing it, its po- tential for use in machine translation and TAG se- mantics systems is limited. Given a particular grammar, the polynomial de- gree of efficient STAG parsing algorithms depends directly on the rank of the grammar: the maximum number of correspondences that appear within a sin- gle elementary structure. This is illustrated by the tree pairs given in Figure 1 in which no two num- bered links may be isolated. (By “isolated”, we mean that the links can be contained in a fragment of the tree that contains no other links and domi- nates only one branch not contained in the fragment. A precise definition is given in section 3.) An …

Content truncated to 500 words