Optimal k-arization of synchronous tree-adjoining grammar

DSpace/Manakin Repository

Optimal k-arization of synchronous tree-adjoining grammar

Citable link to this page

. . . . . .

Title: Optimal k-arization of synchronous tree-adjoining grammar
Author: Nesson, Rebecca; Shieber, Stuart; Satta, Giorgio

Note: Order does not necessarily reflect citation order of authors.

Citation: Rebecca Nesson, Giorgio Satta, and Stuart M. Shieber. Optimal k-arization of synchronous tree-adjoining grammar. In Proceedings of the Ninth International Workshop on Tree Adjoining Grammars and Related Formalisms (TAG+ 9), Tübingen, Germany, 7-8 June 2008.
Full Text & Related Files:
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 nonterminal 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| · (L_G)^3 ) time where L_G 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.
Published Version: http://www.aclweb.org/anthology-new/P/P08/P08-1069.pdf
Terms of Use: This article is made available under the terms and conditions applicable to Other Posted Material, as set forth at http://nrs.harvard.edu/urn-3:HUL.InstRepos:dash.current.terms-of-use#LAA
Citable link to this page: http://nrs.harvard.edu/urn-3:HUL.InstRepos:2309661

Show full Dublin Core record

This item appears in the following Collection(s)

  • FAS Scholarly Articles [7456]
    Peer reviewed scholarly articles from the Faculty of Arts and Sciences of Harvard University
 
 

Search DASH


Advanced Search
 
 

Submitters