Publication
Partially ordered multiset context-free grammars and free-word-order parsing
Mark-Jan Nederhof; Giorgio Satta; Stuart M. Shieber
In: Proceedings of the 8th International Workshop on Parsing Technologies (IWPT'03), April 23-25. International Conference on Parsing Technologies (IWPT), Nancy, France, Pages 171-182, 2003.
Abstract
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.