dc.contributor.author | Nederhof, Mark-Jan | |
dc.contributor.author | Satta, Giorgio | |
dc.contributor.author | Shieber, Stuart | |
dc.date.accessioned | 2008-11-10T19:44:29Z | |
dc.date.issued | 2003 | |
dc.identifier.citation | Mark-Jan Nederhof, Giorgio Satta, and Stuart M. Shieber. Partially ordered multiset context-free grammars and ID/LP parsing. In Proceedings of the Eighth International Workshop on Parsing Technologies, pages 171-182, Nancy, France, April 2003. | en |
dc.identifier.uri | http://nrs.harvard.edu/urn-3:HUL.InstRepos:2252599 | |
dc.description.abstract | We present a new formalism, partially ordered multiset context-free grammars (poms-CFG), along with an Earley-style parsing algorithm. The formalism, which can be thought of as a generalization of context-free grammars with partially ordered right-hand sides, is of interest in its own right, and also as infrastructure for obtaining tighter complexity bounds for more expressive context-free formalisms intended to express free or multiple word-order, such as ID/LP grammars. We reduce ID/LP grammars to poms-grammars, thereby getting finer-grained bounds on the parsing complexity of ID/LP grammars. We argue that in practice, the width of attested ID/LP grammars is small, yielding effectively polynomial time complexity for ID/LP grammar parsing. | en |
dc.description.sponsorship | Engineering and Applied Sciences | en |
dc.language.iso | en_US | en |
dc.publisher | Association for Computational Linguistics | en |
dc.relation.isversionof | http://hmi.ewi.utwente.nl/sigparse/iwpt2003/shieber.pdf | en |
dash.license | LAA | |
dc.title | Partially ordered multiset context-free grammars and ID/LP parsing | en |
dc.relation.journal | Proceedings of the Eighth International Workshop on Parsing Technologies | en |
dash.depositing.author | Shieber, Stuart | |
dash.identifier.orcid | 0000-0002-7733-8195 | * |
dash.contributor.affiliated | Shieber, Stuart | |