M. Hepple. 1996. A Compilation-Chart Method for Linear Categorial Deduction. Proceedings of the 16th International Conference on Computational Linguistics (COLING'96). pp 537-542. Copenhagen, August 1996.

Abstract:

Recent work in categorial grammar has seen proposals for a wide range of systems, differing in their `resource sensitivity' and hence, implicitly, their underlying notion of `linguistic structure'. A common framework for parsing such systems is emerging, whereby some method of linear logic theorem proving is used in combination with a system of labelling that ensures that only deductions appropriate to the relevant categorial formalism are allowed. This paper presents a deduction method for implicational linear logic that brings with it the benefit that chart parsing provides for CFG parsing, namely avoiding the need to recompute intermediate results when searching exhaustively for all possible analyses. The method involves compiling possibly higher-order linear formulae to indexed first-order formulae, over which deduction is made using just a single inference rule.