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.