August 15 – 17 , 1990, Dagstuhl Seminar 9033

Tree Adjoining Grammars


K. Harbusch, W. Wahlster

For support, please contact

Dagstuhl Service Team


Dagstuhl's Impact: Documents available
Dagstuhl-Seminar-Report 2


The topic of the workshop was a grammar formalism - the Tree Adjoining Grammars (TAGs) - which has interesting formal properties (e.g., mild contextsensitivity) as well as a wide range of application domains, especially in the field of natural language processing. Thus, it was very fruitful for the discussions to bring together researchers from both areas of interest in TAGs.

TAGs were introduced in 1975 by Joshi, Levy and Takahashi ([Joshi et al. 75]). To get a first intuition of the formalism - for a good introduction see [Joshi 85] - one can think of TAG rules as combined context-free rules building a context-free derivation tree. These trees are called initial trees. A second class of rules - the auxiliary trees - which are necessary for describing arbitrary large TAG-derivation trees - are characterized by a special nonterminal leave - the foot node) - in the context-free derivation tree which carries the same label as the root node. The adjoining operation replaces a nonterminal node in an initial tree (which can be modified by former adjoinings) by an auxiliary tree. This means that the incoming edge in the root node will end in the root node of the auxiliary tree and all outgoing edges of the eliminated node will start in the foot node of the auxiliary tree. Obviously a derivation tree results again.

The TAG formalism was introduced as an adequate formalism for encoding natural language grammars referring to the property of mild context-sensitivity. There is strong evidence in the linguistic community that this is the right complexity for natural language description.

The workshop dealt with various problems in the formal area, e.g., extensions for the pure TAG formalism, automata models for the grammar representation or efficient parsing algorithms. Most investigations were motivated by specific applications (e.g., natural language parsing and generation, help systems)

In this interdisciplinary field of computer science, computational linguistics and psycholinguistics the talks found interesting feedback and a lot of very fruitful discussions went on during the three days.


In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.


Download overview leaflet (PDF).

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.


Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.