Paper: Optimal $k$-arization of Synchronous Tree-Adjoining Grammar

ACL ID P08-1069
Title Optimal $k$-arization of Synchronous Tree-Adjoining Grammar
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 2008

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 ...