Convertir des grammaires d'arbres adjoints à composantes multiples avec tuples d'arbres (TT-MCTAG) en grammaires à concaténation d'intervalles (RCG)

Résumé : Cet article étudie la relation entre les grammaires d'arbres adjoints à composantes multiples avec tuples d'arbres (TT-MCTAG), un formalisme utilisé en linguistique informatique, et les grammaires à concaténation d'intervalles (RCG). Les RCGs sont connues pour décrire exactement la classe PTIME, il a en outre été démontré que les RCGs "simples" sont même équivalentes aux systèmes de réécriture hors-contextes linéaires (LCFRS), en d'autres termes, elles sont légèrement sensibles au contexte. TT-MCTAG a été proposé pour modéliser les langages à ordre des mots libre. En général ces langages sont NP-complets. Dans cet article, nous définissons une contrainte additionnelle sur les dérivations autorisées par le formalisme TT-MCTAG. Nous montrons ensuite comment cette forme restreinte de TT-MCTAG peut être convertie en une RCG simple équivalente. Le résultat est intéressant pour des raisons théoriques (puisqu'il montre que la forme restreinte de TT-MCTAG est légèrement sensible au contexte), mais également pour des raisons pratiques (la transformation proposée ici a été utilisée pour implanter un analyseur pour TT-MCTAG).
Type de document :
Communication dans un congrès
15e Conférence sur le Traitement Automatique des Langues Naturelles - TALN 2008, Jun 2008, Avignon, France. pp._, 2008
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00275070
Contributeur : Yannick Parmentier <>
Soumis le : mardi 22 avril 2008 - 13:45:17
Dernière modification le : jeudi 23 août 2012 - 17:03:15
Document(s) archivé(s) le : jeudi 20 mai 2010 - 23:32:38

Fichiers

ttmctag-rcg.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00275070, version 1

Citation

Laura Kallmeyer, Yannick Parmentier. Convertir des grammaires d'arbres adjoints à composantes multiples avec tuples d'arbres (TT-MCTAG) en grammaires à concaténation d'intervalles (RCG). 15e Conférence sur le Traitement Automatique des Langues Naturelles - TALN 2008, Jun 2008, Avignon, France. pp._, 2008. 〈inria-00275070〉

Partager

Métriques

Consultations de la notice

66

Téléchargements de fichiers

76