Expressiveness and Complexity in Underspecified Semantic Representation
                                              Shalom Lappin
                                         King's College London
                    (joint work with Chris Fox, CS, University of Essex)

We address a central issue in the development of an adequate formal theory
of underspecified semantics. The tension between expressive power and computational
tractability poses an acute problem for any such theory. Ebert (2005) shows that any reasonable
treatment of underspecified semantic representation either suffers from expressive
incompleteness, or produces a combinatorial explosion that is equivalent to generating the
full set of possible scope readings in the course of disambiguation. In Fox and Lappin (2005) we
presented an account of underspecified scope representations within Property Theory
with Curry Typing (PTCT), an intensional first-order theory for natural language semantics.
We review this account, and we show that filters applied to the underspecified-scope terms
of PTCT permit expressive completeness. While they do not solve the general complexity
problem, they can significantly reduce the search space for computing the full set of resolved
scope readings in non-worst cases.