Programming in Logic with Constraints for Natural Language Processing

Programming in Logic with Constraints for Natural Language Processing Patrick Saint-Dizier LSI UniversiM Paul Sabatier 118 route de Narbonne 31062 TOULOUSE Cedex France Abstract In this paper, we present a logic-based computational model for movement theory in Government and Binding Theory. For that purpose, we have designed a language called DISLOG. DISLOG stands for programming in logic with discontinuities and permits to express in a simple, concise and declarative way relations or constraints between non-contiguous elements in a structure. DISLOG is also weel adapted to model other types of linguistic phenomena like Quantifier Raising involving long-distance relations or constraints. 1. Introduction Many areas of natural language syntax and semantics are a fruitful source of inspiration for computer languages and systems designers. The complexity of natural language and the high level of abstraction of most linguistic and semantic theories have motivated the emergence of highly abstract and transparent programming languages. One of the most striking examples is undoubtedly Prolog, initially designed for natural language parsing, via Metamorphosis Grammars (Colmerauer 1978). For a few years, the Logic Programming paradigm has been augmented with a number of technical and formal devices designed to extend its expressive power. New logic programming languages have emerged, several of them motivated by natural language processing problems. Among them let us mention: CIL (Mukai 1985), designed to express in a direct way concepts of Situation Semantics, MOLOG (Farinas et al. 1985), an extension to Prolog designed to specify in a very simple and declarative way the semantics of modal operators and ~,-Prolog (Nadathur and Miller 1988), designed to deal with X-expressions and X-reduction. Recently, the Logic Programming paradigm has been augmented with the concept of constrained logic programming (CLP). The basic research done within this area amounts to specifying tools for a more refined control on the type of values or terms a variable in a program can stand for. Answers to goals can be intensional: they are sets of equations (constraints) rather than mere values. Furthermore, the idea at the operational level, incorrect assignments are filtered out as soon as they are encountered when building a proof, making thus proof procedures more efficient. In this document, we deal with a new, original, type of CLP mechanism: constraints on proof trees. This type of constraint has emerged from, in particular, the definition of a computational model for the quantifier raising operation and for movement theory in Government and Binding theory (noted hereafter as GB). We model those phenomena in terms of constraints between non-contiguous elements in a structure. For example, we want to express constraints between a moved constituent and its co-indexed trace. Constraints are expressed in terms of relations between subtrees in a syntactic tree or in terms of relations between parenthetized constituents in the now more commonly adopted annotated surface forms of sentences. We have designed Dislog, programming in logic with discontinuities, which permits to express relations between non-contiguous elements in a structure in a simple, declarative and concise way. Dislog is an extension to Prolog; …

Content truncated to 500 words