@inproceedings{nederhof-etal-2003-partially,
    title = "Partially Ordered Multiset Context-free Grammars and Free-word-order Parsing",
    author = "Nederhof, Mark-Jan  and
      Satta, Giorgio  and
      Shieber, Stuart",
    booktitle = "Proceedings of the Eighth International Conference on Parsing Technologies",
    month = apr,
    year = "2003",
    address = "Nancy, France",
    url = "https://preview.aclanthology.org/fix-sig-urls/W03-3020/",
    pages = "171--182",
    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."
}