A constraint-programming approach to parsing with resource-sensitive categorial grammar
Katrin Erk, Geert-Jan M. Kruijff · 2002
Parsing with resource-sensitive categorial grammars (up to the LambekVan Benthem calculus LP) is an NP-complete problem. The traditional approach to parsing with such grammars is based on generate & test and cannot avoid this high worst-case complexity. This paper proposes an alternative approach, based on constraint programming: Given a grammar, constraints formulated on an abstract interpretation of the grammar's logical structure are used to prune the search space during parsing. The approach is provably sound and complete, and reduces the search space in steps that are mostly linear or low-polynomial.