Constraint Languages for Semantic Underspecification
Author: Alexander Koller
Editor:
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.
|