Linear context-free rewriting systems (LCFRSs) are grammar formalisms with the capability of modeling discontinuous 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 efficient 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.
['Carlos Gómez-Rodríguez', 'Giorgio Satta']
An Optimal-Time Binarization Algorithm for Linear Context-Free Rewriting Systems with Fan-Out Two