Paper: Relating Complexity To Practical Performance In Parsing With Wide-Coverage Unification Grammars

ACL ID P94-1040
Title Relating Complexity To Practical Performance In Parsing With Wide-Coverage Unification Grammars
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 1994
Authors

The paper demonstrates that exponential com- plexities with respect to grammar size and input length have little impact on the performance of three unification-based parsing algorithms, using a wide-coverage grammar. The results imply that the study and optimisation of unification-based parsing must rely on empirical data until complex- ity theory can more accurately predict the practi- cal behaviour of such parserQ.