DFKI-LT - Dissertation Series

Vol. XIV

Katrin Erk: Parallelism Constraints in Underspecified Semantics

ISBN: 3-933218-13-6
298 pages
price: € 16

order form

This thesis studies a constraint language that is interpreted over lambda terms represented as tree-like structures. The language has been developed in the context of natural language semantics, where it is used for an underspecified representation of meaning. Our main focus is on determining satisfiability of these constraints, in particular for a construct of this constraint language that can be used to model parallelism phenomena.

The constraint language that we study is the Constraint Language for Lambda Structures (CLLS), and the language construct that we focus on is the parallelism constraint. Parallelism constraints are formulas that state that two pieces of a tree have the same structure. The central issue of this thesis is the processing of parallelism constraints.

An important characteristic of CLLS is that it allows for statements of parallelism on a description that leaves open the relative position of tree nodes. We consider two related applications of parallelism constraints, which both centrally make use of this property. First, the language CLLS has been developed as a formalism for underspecified natural language semantics. In this framework, parallelism constraints have been used to model the parallelism phenomenon, which is ubiquitous in linguistics. Prominent examples of parallelism are elliptical constructions like "John sleeps, and Mary does, too". The second application is underspecified beta reduction. The idea is to perform beta reduction on the partial descriptions of lambda terms, rather than on the terms themselves.

This thesis consists of two parts. The first part presents the central contribution: a procedure for solving parallelism constraints. The second part of the thesis studies questions of the practical applicability of the formalism as well as the procedure.

Solving parallelism constraints. We present a sound and complete semi-decision procedure for parallelism constraints and extend it to a semi-decision procedure for CLLS. It has the following properties:

Applicability. In the context of the two applications named above, underspecified natural language semantics and underspecified beta reduction, the thesis focuses on two issues:

For both issues, the notion of correspondence again proves essential.