Parallelism constraints in underspecified semantics

Abstract

This thesis studies the Constraint Language for Lambda Structures (CLLS), which is interpreted over lambda terms represented as tree-like structures. Our main focus is on the processing of parallelism constraints, a construct of CLLS. A parallelism constraint states that two pieces of a tree have the same structure. We present a sound and complete semi-decision procedure for parallelism constraints, which tests satisfiability and makes structural isomorphism explicit. This procedure is extended to a semi-decision procedure for CLLS. We discuss two applications of CLLS. First, CLLS has been developed as a formalism for underspecified natural language semantics. In this context, parallelism constraints are used for modeling parallelism phenomena. Second, we consider underspecified beta reduction, which is beta reduction on partial descriptions of lambda terms. For these application areas, we present extensions both to the language CLLS and to the semi-decision procedure.

Diese Dissertation untersucht die Constraint Language for Lambda Structures (CLLS),eine Constraint-Sprache zur Beschreibung von Lambda-Termen in einer baum- ähnlichen Repräsentation. Der Schwerpunkt der Arbeit liegt auf Verfahren für Parallelismus-Constraints, ein Konstrukt der Sprache CLLS. Ein Parallelismus-Constraint besagt, dass zwei Bereiche eines Baumes dieselbe Struktur haben. Wir stellen ein korrektes und vollständiges Semi-Entscheidungsverfahren für Parallelismus-Constraints vor, das Erfüllbarkeit feststellt und Strukturgleichheitexplizit macht. Dies Verfahren wird zu einem Semi-Entscheidungsverfahren für CLLS erweitert. Wir diskutieren zwei Anwendungen der Sprache CLLS. Zum einen ist CLLS als Beschreibungsformalismus für unterspezifizierte natürlichsprachliche Semantik entwickelt worden. In diesem Zusammenhang werden Parallelismus-Constraints zur Modellierung von Parallelismus-Phänomenen verwendet. Zum anderen betrachten wir unterspezifizierte Beta-Reduktion, Beta-Reduktion auf partiellen Beschreibungen von Lambda-Termen. Für diese Anwendungsgebiete stellen wir Erweiterungen sowohl der Sprache CLLS als auch des Semi-Entscheidungsverfahrens vor.