DFKI-LT - Dissertation Series

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:

• The procedure is stated in terms of high-level transformation rules.
• The procedure computes constraints from which models can be directly read off. In particular, it computes all minimal constraints with this property for a given input constraint. During the computation, structural isomorphism imposed by parallelism constraints is made explicit.
• The procedure terminates on the classes of cases relevant for the applications.
• The central concept of the procedure is correspondence: In accordance with the node-centered perspective on trees that CLLS adopts, the procedure relates nodes that occupy matching positions in the two parallel tree pieces.

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

• Empirical adequacy: Is the formal language adequate for modeling the phenomena arising both in underspecified beta reduction and in underspecified semantics? We present two extensions to the standard CLLS formulation of parallelism constraints, which are of use both for underspecified beta reduction and for modeling ellipsis.
• Underspecification: In solving parallelism constraints, the above procedure makes the relative position of nodes explicit. However it may be desirable to maintain underspecification as far as possible while making structural isomorphism explicit. We discuss a procedure which, exploiting knowledge about the relative positions of parallel tree pieces in underspecified beta reduction, can avoid disambiguation in many cases.

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