Paper: The Computational Difficulty Of ID/LP Parsing

ACL ID P85-1010
Title The Computational Difficulty Of ID/LP Parsing
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 1985

lodern linguistic theory attributes surface complexity to interacting snbsystems of constraints. ["or instance, the ID LP gr,'unmar formalism separates constraints on immediate dominance from those on linear order. 5hieber's (t983) ID/I.P parsing algorithm shows how to use ID and LP constraints directly in language process- ing, without expandiqg them into an intcrmrdiate "object gammar". However, Shieber's purported O(:,Gi 2 .n ~) run- time bound underestimates the tlillicnlty of ID/LP parsing. ID/LP parsing is actually NP-complete, anti the worst-case runtime of Shieber's algorithm is actually exponential in grammar size. The growth of parser data structures causes the difficulty. So)tie ct)mputational and linguistic implica- tions follow: in particular, it is important to note that desp...