supervised by: Marco Kuhlmann

Abstract

Lexicalised Configuration Grammars (LCG) is a declarative framework for non-projective dependency grammars. Lexical entries in LCG are local well-formedness conditions for drawings (trees equipped with a total order). The framework is powerful enough to encode a large number of existing grammar formalisms declaratively.

The expressivity of LCG, however, comes at the cost of NP-complete word problems and parsing complexities that are hard to analyse. This diploma thesis shows that by borrowing efficient parsing concepts from generative formalisms, the computational factors that contribute to complexity can be formalised and isolated. A variety of possibilities to restrict these factors is elaborated in order to reduce complexity to polynomial time.

Moreover, a precise analysis is presented for a specifc LCG grammar formalism with precedence and discontinuity constraints. By combining the complexity results, that formalism is proven to allow for declarative definitions of mildly context-sensitive languages, which are believed to sufficiently account for many natural languages.

Downloads

• Diploma thesis (PDF)
• Slides of the final talk (PDF)

Status

Current ideas and information on the progress did appear in my thesis blog (in German).