Optimal rank reduction for Linear Context-Free Rewriting Systems with Fan-Out Two - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2010

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

Résumé

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.
Fichier principal
Vignette du fichier
acl2010lcfrs.pdf (280.02 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00515455 , version 1 (07-09-2010)
inria-00515455 , version 2 (24-05-2015)
inria-00515455 , version 3 (16-06-2020)

Identifiants

  • HAL Id : inria-00515455 , version 3

Citer

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⟩
310 Consultations
103 Téléchargements

Partager

Gmail Facebook X LinkedIn More