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.
Diploma thesis
Slides of the final
talk (Power Point file)