Publication: Partially ordered multiset context-free grammars and ID/LP parsing
Open/View Files
Date
2003
Published Version
Published Version
Journal Title
Journal ISSN
Volume Title
Publisher
Association for Computational Linguistics
The Harvard community has made this article openly available. Please share how this access benefits you.
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.
Research Data
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.
Description
Other Available Sources
Keywords
Terms of Use
This article is made available under the terms and conditions applicable to Other Posted Material (LAA), as set forth at Terms of Service