The Computational Difficulty of ID/LP Parsing

THE COMPUTATIONAL DIFFICULTY OF ID/LP PARSING G. Edward Barton, Jr. M.I.T. Artificial Intelligence Laboratory 545 Technology Square Caanbridge, MA 02139 ABSTRACT .\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 despite its poteutial for combinatorial explosion, Shieber's algorithm remains better thau the alternative of parsing an expanded object gr~anmar. INTRODUCTION Recent linguistic theories derive surface complexity fr~ml modular subsystems of constraints; Chotusky (1981:5) proposes separate theories of bounding, government, O-marking, and so forth, while G,'xzdar and ['ullum's GPSG fi)rmalism (Shieber. 1983:2ff) use- immediate-donfinance ¢[D) rules, linear-precedence (l,P) constraints, and ,netarules. When modular ctmstraints ,xre involved, rule systems that multiply out their surface effects are large and clumsy (see Barton. 1984a). "['he expanded context- free %bjeet grammar" that nmltiplies out tile constraints in a typical (,PSG system would contain trillions of rules (Silieber, 1983:1). 5bicher (198:1) thus leads it: a welconte direction by ,.hw.ving how (D,[.P grammars can be parsed "directly," wit hour the combinatorially explosive step of nmltiplying mtt the effects of the [D and LP constraints. Shieber's • dqorithm applies ID and LP constraints one step at a ;ime. ;,s needed, ttowever, some doubts about computa- tion;d complexity remain. ~hieber (198.3:15) argates that his algorithm is identical to Earley's in time complexity, but this result seems almost too much to hope for. An ll)/f.I ) grammar G can be much smalhr th;m an equiva- lent context-free gr,'umnar G'; for example, if Gt contains only the rule ,5 ~to abcde, the corresponding G~t contains 5! ~- 120 rules. If Shieber's algorithm has the same time complexity ~ Earley's. this brevity of exprd~slon comes free (up to a constant). 5hieber ~ays little to ;dlay possible doubts: W,, will t.,r proq,nt a rigor..s (h.lllOtlstr'~..li¢)t) of I'llnP c'(,mpt,'xlty. I.,t ~t .I.,.id b~, ch..tr fr.m tiw oh,.',, rc.lation h,.t w,',.n ) he l,rt,,,vtlt(',l ;tl~,nt hm ;rod E.rt<.y'~ t hat the ('+,t.ph'xity Is )h;d of Earh.y'> ;tig,)rltl~tlt [II t.l.+ worst ,'.:+,,. wh,,re tl.. I.I" rnh'. ;dw:ty:. +p,'('ffy ;t tllli(llll" ordor- t;,~ l'-r t!+(. ri~i~t-imlld :~+'(' ,,l'<,v<."y ID rtih., the l)i'('r~'tlte~l ;d.,;,with;'. r,,,In."v., t.+ E,trh'y, ;tl~t)rllhlll ~qin,.+, ~ivon )h,' ..:ramm.tr. vht.rkm~ :I.. LI) rnh.:.; t;Lk(..., Cl)ll+'r+liillt time. rh,,. thin. c,)IJHd,,'.":it y ,,I it.. pre>ented :d~.,rltht. i..., ideo- tw;d t() E.ri(.y'+ . That i:.. it ts (it (,' '2 .'t:;). wht.ro :(';: t> )1., qzt' ,,f thv gramt,~ar im,ml,vr ,,f [D ruh'.~) and n i. ~ tilt' h'ngth <)f the input. (:i,If) Among other …

Content truncated to 500 words