Search the Dagstuhl Website
Looking for information on the websites of the individual seminars? - Then please:
Not found what you are looking for? - Some of our services have separate websites, each with its own search option. Please check the following list:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Within this website:
External resources:
Within this website:
External resources:
  • the dblp Computer Science Bibliography

Dagstuhl Seminar 9033

Tree Adjoining Grammars

( Aug 15 – Aug 17, 1990 )

Please use the following short url to reference this page:

  • K. Harbusch
  • W. Wahlster

  • 1st international workshop on tree adjoining grammers : formal theory and application - Wolfgang Wahlster; Harbusch, Karin - Wadern-Dagstuhl : IBFI, 1990. - 101 S..


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.


  • K. Harbusch
  • W. Wahlster