Efficient Parsing with the Product-Free Lambek Calculus

摘要

This paper provides a parsing algorithm for the Lambek calculus which is polynomial time for a more general fragment of the Lambek calculus than any previously known algorithm. The algorithm runs in worst-case time O(n~5) when restricted to a certain fragment of the Lambek calculus which is motivated by empirical analysis. In addition, a set of parameterized inputs are given, showing why the algorithm has exponential worst-case running time for the Lambek calculus in general.