Tree parsing with synchronous tree-adjoining grammars

Matthias B¨uchse, Mark Jan Nederhof, Heiko Vogler

Research output: Chapter in Book/Report/Conference proceedingConference contribution

7 Citations (Scopus)
3 Downloads (Pure)


Restricting the input or the output of a grammar-induced translation to a given set of trees plays an important role in statistical machine translation. The problem for practical systems is to find a compact (and in particular, finite) representation of said restriction. For the class of synchronous tree adjoining
grammars, partial solutions to this problem have been described, some being
restricted to the unweighted case, some to the monolingual case. We introduce a formulation of this class of grammars which is effectively closed under input and output restrictions to regular tree languages, i.e., the restricted translations can again be represented by grammars. Moreover, we present an algorithm that constructs these grammars for input and output restriction, which is inspired
by Earley’s algorithm.
Original languageEnglish
Title of host publicationProceedings of the 12th International Conference on Parsing Technologies (IWPT 2011)
Place of PublicationStroudsburg, PA
PublisherAssociation for Computational Linguistics
Number of pages12
ISBN (Print)978-1932432-04-6
Publication statusPublished - 5 Oct 2011
Event12th International Conference on Parsing Technologies - Dublin, Ireland
Duration: 5 Oct 20107 Oct 2010


Conference12th International Conference on Parsing Technologies


  • Parsing algorithms
  • Natural language processing


Dive into the research topics of 'Tree parsing with synchronous tree-adjoining grammars'. Together they form a unique fingerprint.

Cite this