Skip to Main content Skip to Navigation
Conference papers

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.
Complete list of metadatas

Cited literature [9 references]  Display  Hide  Download

https://hal.inria.fr/inria-00232587
Contributor : Yannick Parmentier <>
Submitted on : Friday, February 1, 2008 - 11:04:37 AM
Last modification on : Thursday, April 30, 2020 - 10:48:25 AM
Long-term archiving on: : Monday, May 3, 2010 - 4:08:04 PM

File

ttmctag-rcg.pdf
Files produced by the author(s)

Identifiers

  • 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), Research Group on Mathematical Linguistics at Universitat Rovira i Virgili University, Mar 2008, Tarragona, Spain. pp.263-274. ⟨inria-00232587⟩

Share

Metrics

Record views

315

Files downloads

572