Paper: Range Concatenation Grammars for Translation

ACL ID C08-2026
Title Range Concatenation Grammars for Translation
Venue International Conference on Computational Linguistics
Session Poster Session
Year 2008

Positive and bottom-up non-erasing bi- nary range concatenation grammars (Boul- lier, 1998) with at most binary predicates ((2,2)-BRCGs) is a O(|G|n6) time strict extension of inversion transduction gram- mars (Wu, 1997) (ITGs). It is shown that (2,2)-BRCGs induce inside-out align- ments (Wu, 1997) and cross-serial discon- tinuous translation units (CDTUs); both phenomena can be shown to occur fre- quently in many hand-aligned parallel cor- pora. A CYK-style parsing algorithm is introduced, and induction from aligment structures is briefly discussed. Range concatenation grammars (RCG) (Boul- lier, 1998) mainly attracted attention in the for- mal language community, since they recognize ex- actly the polynomial time recognizable languages, but recently they have been argued to be useful for...