Skip to Main content Skip to Navigation
Conference papers

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 metadata

Cited literature [13 references]  Display  Hide  Download

https://hal.inria.fr/inria-00515455
Contributor : Benoît Sagot <>
Submitted on : Tuesday, June 16, 2020 - 4:57:47 PM
Last modification on : Thursday, February 11, 2021 - 2:38:02 PM

File

acl2010lcfrs.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00515455, version 3

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-00515455v3⟩

Share

Metrics

Record views

12

Files downloads

116