Feature Constraint Grammars

Abstract

Die vorliegende Dissertation befasst sich mit den logischen Grundlagen von constraint-basierten Grammatikformalismen und deren Modellierung auf einem Computer. Unter Modellierung auf einem Computer verstehen wir das Austesten der empirischen Vorhersagen einer Grammatik auf einem Computer. Dies subsumiert z.B. das Parsingproblem: gegeben eine Grammatik und eine Zeichenkette (Satz), ist dieser Satz grammatisch oder ungrammatisch? Die verwendete Logik ist eine getypte Attribut-Wert-Logik, die als Logik zur Formalisierung von HPSG vorgeschlagen wurde. Die vorliegende Arbeit konzentriert sich dabei sowohl auf die theoretischen Eigenschaften der Logik, als auch praktische algorithmische Aspekte. Es werden Algorithmen für die Modellierung angegeben, und deren Korrektheit bezüglich der zugrunde liegenden Logik bewiesen.

This thesis is concerned with the logical foundations and computational modeling of constraint-based grammar formalisms. By computational modeling I understand the testing of the empirical predictions of a given grammar on a computer. This subsumes, e.g., the parsing problem: given a grammar and a string, does the grammar predict that the string is grammatical, or ungrammatical? The logic under consideration is a typed feature logic, that may be viewed as a basis for formalizing HPSG grammars. The thesis has a dual focus on theory and computation. I give algorithms for solving the prediction problem, and the algorithms are proven correct with respect to the underlying logic.