Efficiently Parsing with the Product-Free Lambek Calculus

Proceedings of the 22nd International Conference on Computational Linguistics (Coling 2008), pages 217–224 Manchester, August 2008 Efficient Parsing with the Product-Free Lambek Calculus Timothy A. D. Fowler Department of Computer Science University of Toronto 10 King’s College Road, Toronto, ON, M5S 3G4, Canada tfowler@cs.toronto.edu Abstract This paper provides a parsing algorithm for the Lambek calculus which is polyno- mial time for a more general fragment of the Lambek calculus than any previously known algorithm. The algorithm runs in worst-case time O(n5) when restricted to a certain fragment of the Lambek calcu- lus which is motivated by empirical anal- ysis. In addition, a set of parameterized inputs are given, showing why the algo- rithm has exponential worst-case running time for the Lambek calculus in general. 1 Introduction A wide variety of grammar formalisms have been explored in the past for parsing natural language sentences. The most prominent of these for- malisms has been context free grammars (CFGs) but a collection of formalisms known as categorial grammar (CG) (Ajdukiewicz, 1935; Dowty et al., 1981; Steedman, 2000) has received interest be- cause of some significant advantages over CFGs. First, CG is inherently lexicalized due to the fact that all of the variation between grammars is cap- tured by the lexicon. This is a result of the rich categories which CG uses in its lexicon to specify the functor-argument relationships between lexical items. A distinct advantage of this lexicalization is that the processing of sentences depends upon only those categories contained in the string and not some global set of rules. Second, CG has the advantage that it centrally adopts the princi- ple of compositionality, as outlined in Montague c⃝ 2008. Licensed under the Creative Commons Attribution-Noncommercial-Share Alike 3.0 Unported li- cense (http://creativecommons.org/licenses/by-nc-sa/3.0/). Some rights reserved. grammar (Montague, 1974), allowing the semantic derivation to exactly parallel the syntactic deriva- tion. This leads to a semantical form which is eas- ily extractable from the syntactic parse. A large number of CG formalisms have been introduced including, among others, the Lambek calculus (Lambek, 1958) and Combinatory Cat- egorial Grammar (CCG) (Steedman, 2000). Of these, CCG has received the most zealous com- putational attention. Impressive results have been achieved culminating in the state-of-the-art parser of Clark and Curran (2004) which has been used as the parser for the Pascal Rich Textual Entailment Challenge entry of Bos and Markert (2005). The appeal of CCG can be attributed to the existence of efficient parsing algorithms for it and the fact that it recognizes a mildly context-sensitive language class (Joshi et al., 1989), a language class more powerful than the context free languages (CFLs) that has been argued to be necessary for natural language syntax. The Lambek calculus provides an ideal contrast between CCG and CFGs by be- ing a CG formalism like CCG but by recognizing the CFLs like CFGs (Pentus, 1997). The primary goal of this paper is to provide an algorithm for parsing with the Lambek calcu- lus and to sketch its correctness. Furthermore, a time bound …

Content truncated to 500 words