DFKI-LT - Partially ordered multiset context-free grammars and free-word-order parsing

Mark-Jan Nederhof, Giorgio Satta, Stuart M. Shieber
Partially ordered multiset context-free grammars and free-word-order parsing
1 Proceedings of the 8th International Workshop on Parsing Technologies (IWPT'03), April 23-25, Pages 171-182, Nancy, France, 2003
 
We present a new formalism, partially ordered multiset context-freegrammars (poms-CFG), along with an Earley-style parsing algorithm.The formalism, which can be thought of as a generalization ofcontext-free grammars with partially ordered right-hand sides, is ofinterest in its own right, and also as infrastructure for obtainingtighter complexity bounds for more expressive context-free formalismsintended to express free or multiple word-order, such as ID/LPgrammars. We reduce ID/LP grammars to poms-grammars, thereby getting finer-grained bounds on the parsingcomplexity of ID/LP grammars. We argue that in practice, the width ofattested ID/LP grammars is small, yielding effectively polynomial timecomplexity for ID/LP grammar parsing.
 
Files: BibTeX, Nederhof:2003:POM.pdf