Paper: An Optimal-Time Binarization Algorithm for Linear Context-Free Rewriting Systems with Fan-Out Two

ACL ID P09-1111
Title An Optimal-Time Binarization Algorithm for Linear Context-Free Rewriting Systems with Fan-Out Two
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 2009
Authors

Linear context-free rewriting systems (LCFRSs) are grammar formalisms with the capability of modeling discontinu- ous constituents. Many applications use LCFRSs where the fan-out (a measure of the discontinuity of phrases) is not allowed to be greater than 2. We present an ef- ficient algorithm for transforming LCFRS with fan-out at most 2 into a binary form, whenever this is possible. This results in asymptotical run-time improvement for known parsing algorithms for this class.