On the relation between Multicomponent Tree Adjoining Grammars with Tree Tuples (TT-MCTAG) and Range Concatenation Grammars (RCG)

Abstract : This paper investigates the relation between TT-MCTAG, a formalism used in computational linguistics, and RCG. RCGs are known to describe exactly the class PTIME; simple RCG even have been shown to be equivalent to linear context-free rewriting systems, i.e., to be mildly context-sensitive. TT-MCTAG has been proposed to model free word order languages. In general, it is NP-complete. In this paper, we will put an additional limitation on the derivations licensed in TT-MCTAG. We show that TT-MCTAG with this additional limitation can be transformed into equivalent simple RCGs. This result is interesting for theoretical reasons (since it shows that TT-MCTAG in this limited form is mildly context-sensitive) and, furthermore, even for practical reasons: We use the proposed transformation from TT-MCTAG to RCG in an actual parser that we have implemented.
Type de document :
Communication dans un congrès
2nd International Conference on Language and Automata Theory and Applications (LATA 2008), Mar 2008, Tarragona, Spain. pp.263-274, 2008
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00232587
Contributeur : Yannick Parmentier <>
Soumis le : vendredi 1 février 2008 - 11:04:37
Dernière modification le : samedi 7 août 2010 - 16:04:43
Document(s) archivé(s) le : lundi 3 mai 2010 - 16:08:04

Fichier

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

Identifiants

  • HAL Id : inria-00232587, version 1

Citation

Laura Kallmeyer, Yannick Parmentier. On the relation between Multicomponent Tree Adjoining Grammars with Tree Tuples (TT-MCTAG) and Range Concatenation Grammars (RCG). 2nd International Conference on Language and Automata Theory and Applications (LATA 2008), Mar 2008, Tarragona, Spain. pp.263-274, 2008. 〈inria-00232587〉

Partager

Métriques

Consultations de la notice

70

Téléchargements de fichiers

212