Paper: An Earley-Type Recognizer For Dependency Grammar

ACL ID C96-2122
Title An Earley-Type Recognizer For Dependency Grammar
Venue International Conference on Computational Linguistics
Session Main Conference
Year 1996
Authors

The paper is a first attempt to fill a gap in the dependency literature, by providing a mathematical result on the complexity of recognition with a dependency grammar. The paper describes an improved Earley-type recognizer with a complexity O(IGl2n3). The improvement is due to a precompilation of the dependency rules into parse tables, that determine the conditions of applicability of two primary actions, predict and scan, used in recognition.