@MastersThesis{Koller:1999,
      AUTHOR = {Koller, Alexander},
      TITLE = {Constraint Languages for Semantic Underspecification},
      YEAR = {1999},
      ADDRESS = {Saarbrücken},
      SCHOOL = {Computational Linguistics},
      URL = {ftp://ftp.ps.uni-sb.de/pub/papers/ProgrammingSysLab/Koller99.ps.gz},
      ABSTRACT = {At all levels of linguistic analysis, natural language can be ambiguous. The numbers of readings of different ambiguous components of a sentence or discourse multiply over all these components, yielding a number of readings that can be exponential in the number of ambiguities. Both from a computational and a cognitive point of view, it seems necessary to find small representations for ambiguities that describe all readings in a compact way. This approach is called underspecification, and it has received increasing attention in the past few years. Lately, two particularly elegant formalisms for the underspecified treatment of scope ambiguities in semantics have been proposed: Context Unification and the Constraint Language for Lambda Structures, CLLS. Common to both is that they regard the term representing the semantics of a sentence as a tree and describe it by imposing tree constraints. Furthermore, both offer the expressive power to describe simple ellipses and their interaction with scope ambiguities. This thesis investigates some formal properties of these two formalisms. It examines their relation and shows that, except for a few additional constructs of CLLS, both languages are equivalent in expressive power. In terms of computational complexity, this gives us the immediate result that the complexity of the satisfiability problem of CLLS is exactly the same as that of context unification, which, unfortunately, is unknown. The thesis further investigates the complexity of the satisfiability problem of dominance constraints, an important sublanguage of CLLS, and shows that it is NP-complete. In the course of the discussion of complexity, it also briefly explains how techniques from concurrent constraint programming can be applied to implement solution algorithms for these formalisms.},
      ANNOTE = {COLIURL : Koller:1999:CLS.pdf Koller:1999:CLS.ps}
}