Editing Tree-adjoining grammar (section)

==Complexity and application==

Tree-adjoining grammars are more powerful (in terms of [[weak generative capacity]]) than [[context-free grammar]]s, but less powerful than [[linear context-free rewriting system]]s,<ref>Kallmeyer, Laura (2010). Parsing Beyond Context-Free Grammars. Springer. Here: p.215-216</ref> [[indexed grammar|indexed]]<ref group=note>since for each tree-adjoining grammar, a linear indexed grammar can be found producing the same language, see [[#Equivalences|below]], and for the latter, a weakly equivalent (proper) indexed grammar can be found, in turn, see [[Indexed grammar#Computational Power]]</ref> or [[context-sensitive grammar|context-sensitive]] grammars.

A TAG can describe the language of squares (in which some arbitrary string is repeated), and the language <math>\{a^n b^n c^n d^n | 1 \le n \}</math>. This type of processing can be represented by an [[embedded pushdown automaton]].
Languages with cubes (i.e. triplicated strings) or with more than four distinct character strings of equal length cannot be generated by tree-adjoining grammars.

For these reasons, tree-adjoining grammars are often described as [[Mildly context-sensitive grammar|mildly context-sensitive]].
These grammar classes are conjectured to be powerful enough to model [[natural language]]s while remaining efficiently [[parser|parsable]] in the general case.<ref name="joshi1985">{{cite book
 | last = Joshi
 | first = Aravind
 | chapter = How much context-sensitivity is necessary for characterizing structural descriptions
 | year = 1985
 | publisher = Cambridge University Press
 | pages = [https://archive.org/details/naturallanguagep00dowt_276/page/n220 206]–250
 | title = Natural Language Processing: Theoretical, Computational, and Psychological Perspectives
 | url = https://archive.org/details/naturallanguagep00dowt_276
 | url-access = limited
 | editor = D. Dowty |editor2=L. Karttunen |editor3=A. Zwicky
 | location = New York, NY | isbn = 9780521262033
 }}</ref>

===Equivalences===

Vijay-Shanker and Weir (1994)<ref name="vijayshankarAndWeir1995">Vijay-Shanker, K. and Weir, David J. 1994. ''The Equivalence of Four Extensions of Context-Free Grammars''. Mathematical Systems Theory 27(6): 511–546.</ref> demonstrate that [[Indexed grammar#Linear indexed grammars|linear indexed grammars]], [[combinatory categorial grammar]], tree-adjoining grammars, and [[head grammar]]s are [[Weak equivalence (formal languages)|weakly equivalent]] formalisms, in that they all define the same string languages.