Paper: Optimal Rank Reduction for Linear Context-Free Rewriting Systems with Fan-Out Two

ACL ID P10-1054
Title Optimal Rank Reduction for Linear Context-Free Rewriting Systems with Fan-Out Two
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 2010
Authors

Linear Context-Free Rewriting Systems (LCFRSs) are a grammar formalism ca- pable of modeling discontinuous phrases. Many parsing applications use LCFRSs where the fan-out (a measure of the dis- continuity of phrases) does not exceed 2. We present an efficient algorithm for opti- mal reduction of the length of production right-hand side in LCFRSs with fan-out at most 2. This results in asymptotical run- ning time improvement for known parsing algorithms for this class.