In *Proceedings of Mathematics of Language 10*, Los Angeles, California, 2007.

abstract bibtex

abstract bibtex

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. In 2003, Pentus proved that the version of the calculus with the product is NP-complete, while the version which omits the product has a computational complexity that is still unknown. This paper presents graph formalism similar to that of Penn (2001) for the Lambek calculus with product and then examines the differences between the two calculi by way of this new graph formalism.

@InProceedings{ fowler2007, author = {Timothy Alexander Dalton Fowler}, title = {LC Graphs for the {L}ambek calculus with product}, booktitle = {Proceedings of Mathematics of Language 10}, year = {2007}, address = {Los Angeles, California}, abstract = {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. In 2003, Pentus proved that the version of the calculus with the product is NP-complete, while the version which omits the product has a computational complexity that is still unknown. This paper presents graph formalism similar to that of Penn (2001) for the Lambek calculus with product and then examines the differences between the two calculi by way of this new graph formalism.}, download = {http://www.cs.toronto.edu/~tfowler/Fowler-LCGraphsForTheLambekCalculusWithProduct.pdf} }

Downloads: 0