© 1994 by Oxford University Press
Original Articles |
A Hypothetical Reasoning Algorithm for Linguistic Analysis
University of Stuttgart, Institute for Computational Linguistics Azenbergstrasse 12, 70174 Stuttgart 1, GermanyE-mail: esther{at}ims.uni-stuttgart.de
The Lambek calculus, an intuitionistic fragment of linear logic, has recently been rediscovered by linguists. Due to its built-in hypothetical reasoning mechanism, it allows for describing a certain range of those phenomena in natural language syntax which involve incomplete subphrases or moved constituents. Previously, it seemed unclear how to extent traditional parsing techniques in order to incorporate reasoning about incomplete phrases, without causing the undesired effect of derivational equivalences. It turned out that the Larabek calculus offers a framework to formulate equivalent but more implementation-oriented calculi where this problem does not occur. In this paper, such a theorem prover for the Lambek calculus, i.e. a parser for Lambek categorial grammars, is defined. Permutations of proof steps which would cause derivational equivalence in a purely sequential formulation do not play a role in a (pseudo-)parallel approach which is based on a lemma table or a ‘chart’. At the same time, other redundant proof search which would occur in backtracking approaches is avoided.
Keywords: Natural language parsing,; categgorial grammar