Saarland University
Informatics
Programming Systems
Mathias Möhl
Diploma Thesis


Context
Task
Progress
Downloads

Diploma Thesis:

Drawings as Models of Syntactic Structure: Theory and Algorithms

by Mathias Möhl
supervised by Marco Kuhlmann

Context

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.


separator

Task

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.


separator

Progress


separator

Downloads

Diploma thesis
Slides of the final talk (Power Point file)



Valid XHTML 1.0 Strict