A graph formalism for proofs in the Lambek calculus with product.
Published: 2006
Language: eng
Number of pages: 72
ISBN-13: 9780494210598
Description: 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. Several 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.
Notes: Source: Masters Abstracts International, Volume: 45-03, page: 1528.

Thesis (M.Sc.)--University of Toronto, 2006.

Electronic version licensed for access by U. of T. users.

ROBARTS MICROTEXT copy on microfiche.