Article Structure
Abstract
Binarization of grammars is crucial for improving the complexity and performance of parsing and translation.
Introduction
Binarization amounts to transforming a given grammar into an equivalent grammar of rank 2, i.e., with at most two nonterminals on any right-hand side.
Interpreted regular tree grammars
Grammar formalisms employed in parsing and SMT, such as those mentioned in the introduction, differ in the the derived objects—e.g., strings, trees, and graphs—and the operations involved in the derivation—e.g., concatenation, substitution, and adjoining.
IRTG binarization
We will now show how to apply the rule-by-rule binarization technique to IRTGs.
Effective IRTG binarization
In this section we develop our binarization algorithm.
Applications
Algorithm 1 implements rule-by-rule binarization with respect to given b-rules.
Conclusion
We have presented an algorithm for binarizing IRTGs rule by rule, with respect to b-rules that the user specifies for each algebra.
Topics
binarization
- Binarization of grammars is crucial for improving the complexity and performance of parsing and translation.Page 1, “Abstract”
- We present a versatile binarization algorithm that can be tailored to a number of grammar formalisms by simply varying a formal parameter.Page 1, “Abstract”
- We apply our algorithm to binarizing tree-to-string transducers used in syntax-based machine translation.Page 1, “Abstract”
- Binarization amounts to transforming a given grammar into an equivalent grammar of rank 2, i.e., with at most two nonterminals on any right-hand side.Page 1, “Introduction”
- The ability to binarize grammars is crucial for efficient parsing, because for many grammar formalisms the parsing complexity depends exponentially on the rank of the grammar.Page 1, “Introduction”
- The classical approach to binarization , as known from the Chomsky normal form transformation for context-free grammars (CFGs), proceeds rule by rule.Page 1, “Introduction”
- All CFGs can be binarized in thisPage 1, “Introduction”
- Nevertheless, the rule-by-rule binarization algorithm of Huang et al.Page 1, “Introduction”
- In this paper, we offer a generic approach for transferring the rule-by-rule binarization technique to new grammar formalisms.Page 1, “Introduction”
- At the core of our approach is a binarization algorithm that can be adapted to a new formalism by changing a parameter at runtime.Page 1, “Introduction”
- As a consequence, the algorithm bina-rizes every grammar that can be binarized rule by rule.Page 1, “Introduction”
See all papers in Proc. ACL 2013 that mention binarization.
See all papers in Proc. ACL that mention binarization.
Back to top.
subtrees
- 5b): (i) they are equivalent to h1(a) and h2(a), respectively, and (ii) at each node at most two subtrees contain variables.Page 4, “IRTG binarization”
- The variable set of t is the set of all variables that occur in t. The set S(t) of subtree variables of 75 consists of the nonempty variable sets of all subtrees of t. We represent S(t) as a tree v(t), which we call variable tree as follows.Page 5, “IRTG binarization”
- at most two subtrees with variables; and (iii) the terms t1, .Page 5, “IRTG binarization”
See all papers in Proc. ACL 2013 that mention subtrees.
See all papers in Proc. ACL that mention subtrees.
Back to top.
