Since the introduction of the Lambek calculus in Lambek (1958), there has been a great deal of interest in its usefulness as a grammar for parsing in natural language. Sev- eral variants have been introduced and for each, questions of tractability and usefulness have been posited and answered. Pentus (2003) answered the question of tractability of the original calculus by providing an NP-completeness proof.
The simplest of these variants is the version of the original calculus without the product, the computational complexity of which is as yet unknown. This thesis seeks to identify the precise implications of products on the complexity of parsing in the calculus. Towards this goal, a graph formalism for proofs in the original calculus is extended from the work in Penn (2001).
We then present a simplified, graphical NP-completeness proof for derivability in the Lambek calculus with product and consider the potential intractability of the Lambek calculus without product.
", download = "http://www.cs.toronto.edu/~tfowler/MScThesis.pdf" }