%0 Conference Paper %1 eisnerSatta1999 %A Eisner, Jason %A Satta, Giorgio %B Proceedings of the 37th annual meeting of the Association for Computational Linguistics on Computational Linguistics %C Stroudsburg, PA, USA %D 1999 %I Association for Computational Linguistics %K algorithm automaton cfg chart dmv efficient eisner head parsing satta split %P 457--464 %R 10.3115/1034678.1034748 %T Efficient parsing for bilexical context-free grammars and head automaton grammars %U http://dx.doi.org/10.3115/1034678.1034748 %X Several recent stochastic parsers use <i>bilexical</i> grammars, where each word type idiosyncratically prefers particular complements with particular head words. We present <i>O(n</i><sup>4</sup>) parsing algorithms for two bilexical formalisms, improving the prior upper bounds of <i>O(n</i><sup>5</sup>). For a common special case that was known to allow <i>O(n</i><sup>3</sup>) parsing (Eisner, 1997), we present an <i>O(n</i><sup>3</sup>) algorithm with an improved grammar constant. %@ 1-55860-609-3

@inproceedings{eisnerSatta1999, abstract = {Several recent stochastic parsers use <i>bilexical</i> grammars, where each word type idiosyncratically prefers particular complements with particular head words. We present <i>O(n</i><sup>4</sup>) parsing algorithms for two bilexical formalisms, improving the prior upper bounds of <i>O(n</i><sup>5</sup>). For a common special case that was known to allow <i>O(n</i><sup>3</sup>) parsing (Eisner, 1997), we present an <i>O(n</i><sup>3</sup>) algorithm with an improved grammar constant.}, acmid = {1034748}, added-at = {2012-11-02T14:52:58.000+0100}, address = {Stroudsburg, PA, USA}, author = {Eisner, Jason and Satta, Giorgio}, biburl = {https://www.bibsonomy.org/bibtex/2a07d6a549fa698dde22c27256d779cf3/jil}, booktitle = {Proceedings of the 37th annual meeting of the Association for Computational Linguistics on Computational Linguistics}, description = {Efficient parsing for bilexical context-free grammars and head automaton grammars}, doi = {10.3115/1034678.1034748}, interhash = {ac0c552c4e01adb48cbfdd9ffd085c4a}, intrahash = {a07d6a549fa698dde22c27256d779cf3}, isbn = {1-55860-609-3}, keywords = {algorithm automaton cfg chart dmv efficient eisner head parsing satta split}, location = {College Park, Maryland}, numpages = {8}, pages = {457--464}, publisher = {Association for Computational Linguistics}, series = {ACL '99}, timestamp = {2013-11-23T20:11:51.000+0100}, title = {Efficient parsing for bilexical context-free grammars and head automaton grammars}, url = {http://dx.doi.org/10.3115/1034678.1034748}, year = 1999 }