Saarland University

Informatics

Programming Systems

Mathias Möhl

Diploma Thesis

Context

Task

Progress

Downloads

by Mathias Möhl

supervised by Marco Kuhlmann

Tree Adjoining Grammar (TAG) is a grammar formalism that is studied since the 1970's and which allows for more complex linguistic structures than context free grammars, because the local order of constituents does not have to coincide with to the global order in the sentence.

The TAG derivation of a sentence is usually represented by a pair consisting of a derivation tree (representing the history of the derivation) and a derived tree (representing the result of the derivation). The claim which this work is based on is that the derived tree contains mainly redundant information and that the definition of TAGs can be simpified, if the concept of derived trees is abandoned and if all the information that is not redundant is integrated in the derivation trees (Debusmann, Duchier, Kuhlmann and Thater 2004).

A very simple model for the resulting class of linguistic structures
is the one of a *drawing*: A drawing is a tree with a total
order on it's nodes. A TAG derivation *induces* a drawing if
the tree relation of the drawing exactly coincides with the derivation
tree of the TAG derivation and if the order on the nodes of the
drawing is exactly the order on the leaves of the derived
tree. Drawings which are induced by a TAG are in general not
projective: The yield of a node of a drawing is not necessarily convex.

The first goal of the thesis is to define drawings formally and to identify their structural properies: What are appropriate measures for non projectivity? Is the whole class of drawings inducable by TAG grammars? In what respect can drawings be seen as adequate models for TAG?

The second goal of this thesis is to develop, implement and analyse constraint based algorithms for drawings. To reach this aim, a constraint language for drawings should be designed and at least algorithms for the following two problems should be implemented: (a) Decide for a given formula of the constraint language, if there is a drawing that satisfies the formula. (b) Enumerate all drawings that satisfy a given formula of the constraint language.

The work could be extended by an analysis of other grammar formalisms like Multi-Component TAG or Combinatory Categorial Grammar with respect to their relation to drawings.

*7.3.2005:*registration and beginning of work*7.8.2005:*Work on the first goal is finished and published on the*10th Conference on Formal Grammar*and*Ninth Meeting on Mathematics of Language*, Edinburgh, United Kingdom, 2005.*22.02.2006:*I finished work and submitted the final version.

Diploma thesis

Slides of the final
talk (Power Point file)