Partially ordered multiset context-free grammars and ID/LP parsing

DSpace/Manakin Repository

Partially ordered multiset context-free grammars and ID/LP parsing

Citable link to this page

. . . . . .

Title: Partially ordered multiset context-free grammars and ID/LP parsing
Author: Nederhof, Mark-Jan; Shieber, Stuart; Satta, Giorgio

Note: Order does not necessarily reflect citation order of authors.

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.
Full Text & Related Files:
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.
Published Version: http://hmi.ewi.utwente.nl/sigparse/iwpt2003/shieber.pdf
Terms of Use: This article is made available under the terms and conditions applicable to Other Posted Material, as set forth at http://nrs.harvard.edu/urn-3:HUL.InstRepos:dash.current.terms-of-use#LAA
Citable link to this page: http://nrs.harvard.edu/urn-3:HUL.InstRepos:2252599

Show full Dublin Core record

This item appears in the following Collection(s)

  • FAS Scholarly Articles [7213]
    Peer reviewed scholarly articles from the Faculty of Arts and Sciences of Harvard University
 
 

Search DASH


Advanced Search
 
 

Submitters