Advertisement
Published in:
2010 | OriginalPaper | Chapter
A Polynomial Time Algorithm for Parsing with the Bounded Order Lambek Calculus
Author : Timothy A. D. Fowler
Published in: The Mathematics of Language
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
[2] introduced the bounded-order Lambek Calculus and provided a polynomial time algorithm for its sequent derivability. However, this result is limited because it requires exponential time in the presence of lexical ambiguity. That is, [2] did not provide a polynomial time
parsing
algorithm. The purpose of this paper will be to provide such an algorithm. We will prove an asymptotic bound of
O
(
n
4
) for parsing and improve the bound for sequent derivability from
O
(
n
5
) to
O
(
n
3
).