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.
Type de document :
Communication dans un congrès
48th Annual Meeting of the Association for Computational Linguistics - ACL 2010, Jul 2010, Uppsala, Sweden. 2010
Liste complète des métadonnées

Littérature citée [13 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00515455
Contributeur : Benoît Sagot <>
Soumis le : dimanche 24 mai 2015 - 17:29:48
Dernière modification le : jeudi 14 juin 2018 - 10:54:02
Document(s) archivé(s) le : jeudi 20 avril 2017 - 08:15:54

Fichier

acl2010lcfrs.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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. 2010. 〈inria-00515455v2〉

Partager

Métriques

Consultations de la notice

197

Téléchargements de fichiers

66