Can I read The computational difficulty of ID/LP parsing on EtoBox?

The computational difficulty of ID/LP parsing by G. Edward Barton is a scholarly article available to read on EtoBox.

What is The computational difficulty of ID/LP parsing about?

\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 processing, without expandiqg them into an intcrmrdiate "object gammar." However, Shieber's purported O(:,Gi 2 .n ~) runtime 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 implications follow: in particular, it is important to note that despite its poteutial for combinatorial explosion, Shieber's algorithm remains better thau the alternative of parsing an expanded object gr~anmar.

Author

G. Edward Barton

Published

1985

Language

EN