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 Seiten 171-182 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.

Weitere Links

Deutsches Forschungszentrum für Künstliche Intelligenz
German Research Center for Artificial Intelligence