Frank Morawietz
Seminar für Sprachwissenschaft
Theoretische Computerlinguistik
Neuphilologische Fakultät
Universität Tübingen

Frank Morawietz (ed)

Some Aspects of Natural Language Processing and Constraint Programming

Arbeitspapiere des SFB 340, Bericht Nr. 150 (2000), 69pp,
DVI (209kb), PS (312kb), PS.GZ (110kb).

A Non-Generative Contraint-Based Formalism

Philippe Blache and Frank Morawietz


Most of modern linguistic theories rely on the notion of constraints. However, only few applications try to implement the parsing process directly with constraint programming: in most cases, constraints are interpreted in a passive sense, the parsing process itself not being different than the one of classical derivational approaches. We show in this paper that the problem comes from the representation of linguistic information and the generative interpretation of the relation between grammar and language. We propose a new approach, called Property Grammar in which all syntactic information is represented with constraints, the parsing process directly being constraint resolution. Our ideas are implemented using Constraint Handling Rules (Frühwirth, 1998).

Chart Parsing as Contraint Propagation

Frank Morawietz


In this paper, parsing as deduction and constraint programming are brought together to outline a procedure for the specification of constraint-based chart parsers. Extending the proposal in Shieber et al. (1993) which provides a meta interpreter for several deduction systems, we show how to directly realize the inference rules for chart parsers as Constraint Handling Rules (Frühwirth, 1998) by viewing the items of a conventional chart parser as constraints and the constraint base as a chart. This allows the direct use of the constraint resolution process to parse sentences.

Applying Constraint Handling Rules to HPSG

Gerald Penn


Constraint Handling Rules (CHR) have provided a realistic solution to an over-arching problem in many fields that deal with constraint logic programming: how to combine recursive functions or relations with constraints while avoiding non-termination problems. This paper focuses on some other benefits that CHR, specifically their implementation in SICStus Prolog, have provided to computational linguists working on grammar design tools. CHR rules are applied by means of a subsumption check and this check is made only when their variables are instantiated or bound. The former functionality is at best difficult to simulate using more primitive coroutining statements such as SICStus when/2, and the latter simply did not exist in any form before CHR. For the sake of providing a case study in how these can be applied to grammar development, we consider the Attribute Logic Engine (ALE), a Prolog preprocessor for logic programming with typed feature structures, and its extension to a complete grammar development system for Head-driven Phrase Structure Grammar (HPSG), a popular constraint-based linguistic theory that uses typed feature structures. In this context, CHR can be used not only to extend the constraint language of feature structure descriptions to include relations in a declarative way, but also to provide support for constraints with complex antecedents and constraints on the co-occurrence of feature values that are necessary to interpret the type system of HPSG properly.

In case of problems or for comments, please contact:
Last updated: 30-Oct-2000