Tree parsing with synchronous tree-adjoining grammars

Matthias  B¨uchse; Mark Jan Nederhof; Heiko Vogler

Tree parsing with synchronous tree-adjoining grammars

Matthias B¨uchse, Mark Jan Nederhof, Heiko Vogler

School of Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

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 language	English
Title of host publication	Proceedings of the 12th International Conference on Parsing Technologies (IWPT 2011)
Place of Publication	Stroudsburg, PA
Publisher	Association for Computational Linguistics
Pages	14-25
Number of pages	12
ISBN (Print)	978-1932432-04-6
Publication status	Published - 5 Oct 2011
Event	12th International Conference on Parsing Technologies - Dublin, Ireland Duration: 5 Oct 2010 → 7 Oct 2010

Conference

Conference	12th International Conference on Parsing Technologies
Country/Territory	Ireland
City	Dublin
Period	5/10/10 → 7/10/10

Keywords

Parsing algorithms
Natural language processing

Access to Document

W11 2903
(c) 2011 Association for Computational Linguistics, available on ACL anthology website http://aclweb.org/anthology/W/W11/#2900
Accepted author manuscript, 352 KB

Cite this

@inproceedings{f56669b3d901401c92296a16f371dc10,

title = "Tree parsing with synchronous tree-adjoining grammars",

abstract = "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 adjoininggrammars, partial solutions to this problem have been described, some beingrestricted 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 inspiredby Earley{\textquoteright}s algorithm.",

keywords = "Parsing algorithms, Natural language processing",

author = "Matthias B¨uchse and Nederhof, {Mark Jan} and Heiko Vogler",

year = "2011",

month = oct,

day = "5",

language = "English",

isbn = "978-1932432-04-6",

pages = "14--25",

booktitle = "Proceedings of the 12th International Conference on Parsing Technologies (IWPT 2011)",

publisher = "Association for Computational Linguistics",

note = "12th International Conference on Parsing Technologies ; Conference date: 05-10-2010 Through 07-10-2010",

}

TY - GEN

T1 - Tree parsing with synchronous tree-adjoining grammars

AU - B¨uchse, Matthias

AU - Nederhof, Mark Jan

AU - Vogler, Heiko

PY - 2011/10/5

Y1 - 2011/10/5

N2 - 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 adjoininggrammars, partial solutions to this problem have been described, some beingrestricted 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 inspiredby Earley’s algorithm.

AB - 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 adjoininggrammars, partial solutions to this problem have been described, some beingrestricted 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 inspiredby Earley’s algorithm.

KW - Parsing algorithms

KW - Natural language processing

UR - http://aclweb.org/anthology/W/W11/W11-2903.pdf

M3 - Conference contribution

SN - 978-1932432-04-6

SP - 14

EP - 25

BT - Proceedings of the 12th International Conference on Parsing Technologies (IWPT 2011)

PB - Association for Computational Linguistics

CY - Stroudsburg, PA

T2 - 12th International Conference on Parsing Technologies

Y2 - 5 October 2010 through 7 October 2010

ER -

Tree parsing with synchronous tree-adjoining grammars

Abstract

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this