@InProceedings{Erk_Kruijff:2002,
AUTHOR = {Erk, Katrin and Kruijff, Geert-Jan M.},
TITLE = {A Constraint-Programming Approach to Parsing with Resource-Sensitive Categorial Grammar},
YEAR = {2002},
BOOKTITLE = {Proceedings of the 7th International Workshop on Natural Language Understanding and Logic Programming (NLULP'02), July 28},
EDITOR = {Wintner, Shuly},
ADDRESS = {Copenhagen, Denmark},
PUBLISHER = {Computer Science Department, Roskilde University},
URL = {http://www.cs.haifa.ac.il/~shuly/nlulp02/papers/ErkKruijff.pdf},
ABSTRACT = {Parsing with resource-sensitive categorial grammars (up to the Lambek-Van 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.},
ANNOTE = {Erk:2002:CPA}
}
|
