Optimal rank reduction for Linear Context-Free Rewriting Systems with Fan-Out Two

Abstract : Linear Context-Free Rewriting Systems (LCFRSs) are a grammar formalism capable of modeling discontinuous phrases. Many parsing applications use LCFRSs where the fan-out (a measure of the discontinuity of phrases) does not exceed 2. We present an efficient algorithm for optimal reduction of the length of production right-hand side in LCFRSs with fan-out at most 2. This results in asymptotical running time improvement for known parsing algorithms for this class.
Complete list of metadatas

Cited literature [13 references]  Display  Hide  Download

https://hal.inria.fr/inria-00515455
Contributor : Benoît Sagot <>
Submitted on : Sunday, May 24, 2015 - 5:29:48 PM
Last modification on : Thursday, August 29, 2019 - 2:24:09 PM
Long-term archiving on : Thursday, April 20, 2017 - 8:15:54 AM

File

acl2010lcfrs.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00515455, version 2

Collections

Citation

Benoît Sagot, Giorgio Satta. Optimal rank reduction for Linear Context-Free Rewriting Systems with Fan-Out Two. 48th Annual Meeting of the Association for Computational Linguistics - ACL 2010, Jul 2010, Uppsala, Sweden. ⟨inria-00515455v2⟩

Share

Metrics

Record views

367

Files downloads

252