Abstract
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).- Anthology ID:
- 2008.jeptalnrecital-long.14
- Volume:
- Actes de la 15ème conférence sur le Traitement Automatique des Langues Naturelles. Articles longs
- Month:
- June
- Year:
- 2008
- Address:
- Avignon, France
- Editors:
- Frédéric Béchet, Jean-Francois Bonastre
- Venue:
- JEP/TALN/RECITAL
- SIG:
- Publisher:
- ATALA
- Note:
- Pages:
- 131–140
- Language:
- French
- URL:
- https://aclanthology.org/2008.jeptalnrecital-long.14
- DOI:
- Cite (ACL):
- Laura Kallmeyer and Yannick Parmentier. 2008. Convertir des grammaires d’arbres adjoints à composantes multiples avec tuples d’arbres (TT-MCTAG) en grammaires à concaténation d’intervalles (RCG). In Actes de la 15ème conférence sur le Traitement Automatique des Langues Naturelles. Articles longs, pages 131–140, Avignon, France. ATALA.
- Cite (Informal):
- Convertir des grammaires d’arbres adjoints à composantes multiples avec tuples d’arbres (TT-MCTAG) en grammaires à concaténation d’intervalles (RCG) (Kallmeyer & Parmentier, JEP/TALN/RECITAL 2008)
- PDF:
- https://preview.aclanthology.org/ingest-bitext-workshop/2008.jeptalnrecital-long.14.pdf