Algorithms for Generation in Lambek Theorem Proving

ALGORITHMS FOR GENERATION IN LAMBEK THEOREM PROVING Erik-Jan van der Linden * Guido Minnen Institute for Language Technology and Artificial Intelligence Tilburg University PO Box 90153, 5000 LE Tilburg, The Netherlands E-maih vdlindenOkub.nl ABSTRACT We discuss algorithms for generation within the Lambek Theorem Proving Framework. Efficient algorithms for generation in this framework take a semantics-driven strategy. This strategy can be modeled by means of rules in the calculus that are geared to generation, or by means of an al- gorithm for the Theorem Prover. The latter pos- sibility enables processing of a bidirectional cal- culus. Therefore Lambek Theorem Proving is a natural candidate for a 'uniform' architecture for natural language parsing and generation. Keywords: generation algorithm; natural lan- guage generation; theorem proving; bidirection- ality; categorial grammar. 1 INTRODUCTION Algorithms for tactical generation are becoming an increasingly important subject of research in computational linguistics (Shieber, 1988; Shieber et al., 1989; Calder et al., 1989). In this pa- per, we will discuss generation algorithms within the Lambek Theorem Proving (LTP) framework (Moortgat, 1988; Lambek, 1958; van Benthem, 1988). In section (2) we give an introduction to a categorial calculus that is extended towards bidi- rectionality. The naive top-down control strategy in this section does not suit the needs of efficient generation. Next, we discuss two ways to imple- ment a semantics-driven strategy. Firstly, we add inference rules and cut rules geared to generation to the calculus (3). Secondly, since these changes in the calculus do not support bidirectionality, we *We would llke to thank Gosse Bouma, Wietske Si~tsma and Marianne Sanders for their comments on an earlier draft of the paper. 220 introduce a second implementation: a bottom-up algorithm for the theorem prover (4). 2 EXTENDING THE CAL- CULUS Natural Language Processing as deduction The architectures in this paper resemble the uni- form architecture in Shieber (1988) because lan- guage processing is viewed as logical deduction, in analysis and generation: "The generation of strings matching some crite- ria can equally well be thought of as a deductive process, namely a process of constructive proof of the existence of a string that matches the crite- ria." (Shieber, 1988, p. 614). In the LTP framework a categorial reduction sys- tem is viewed as a logical calculus where parsing a syntagm is an attempt to show that it follows from a set of axioms and inference rules. These inference rules describe what the processor does in assembling a semantic representation (representa- tional non-autonomy: Crain and Steedman, 1982; Ades and Steedman, 1982). Derivation trees rep- resent a particular parse process (Bouma, 1989). These rules thus seem to be nondeclarative, and this raises the question whether they can be used for generation. The answer to this question will emerge throughout this paper. Lexical information As in any categorial grammar, linguistic information in LTP is for the larger part represented with the signs in the lex- icon and not with the rules of the calculus (signs are denoted by prosody:syntax:semantlcs). A generator using a categorial grammar needs lex- …

Content truncated to 500 words