<?xml version="1.0" encoding="UTF-8"?>
<modsCollection xmlns="http://www.loc.gov/mods/v3">
<mods ID="nederhof-etal-2003-partially">
    <titleInfo>
        <title>Partially Ordered Multiset Context-free Grammars and Free-word-order Parsing</title>
    </titleInfo>
    <name type="personal">
        <namePart type="given">Mark-Jan</namePart>
        <namePart type="family">Nederhof</namePart>
        <role>
            <roleTerm authority="marcrelator" type="text">author</roleTerm>
        </role>
    </name>
    <name type="personal">
        <namePart type="given">Giorgio</namePart>
        <namePart type="family">Satta</namePart>
        <role>
            <roleTerm authority="marcrelator" type="text">author</roleTerm>
        </role>
    </name>
    <name type="personal">
        <namePart type="given">Stuart</namePart>
        <namePart type="family">Shieber</namePart>
        <role>
            <roleTerm authority="marcrelator" type="text">author</roleTerm>
        </role>
    </name>
    <originInfo>
        <dateIssued>2003-04</dateIssued>
    </originInfo>
    <typeOfResource>text</typeOfResource>
    <relatedItem type="host">
        <titleInfo>
            <title>Proceedings of the Eighth International Conference on Parsing Technologies</title>
        </titleInfo>
        <originInfo>
            <place>
                <placeTerm type="text">Nancy, France</placeTerm>
            </place>
        </originInfo>
        <genre authority="marcgt">conference publication</genre>
    </relatedItem>
    <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.</abstract>
    <identifier type="citekey">nederhof-etal-2003-partially</identifier>
    <location>
        <url>https://aclanthology.org/W03-3020</url>
    </location>
    <part>
        <date>2003-04</date>
        <extent unit="page">
            <start>171</start>
            <end>182</end>
        </extent>
    </part>
</mods>
</modsCollection>

%0 Conference Proceedings
%T Partially Ordered Multiset Context-free Grammars and Free-word-order Parsing
%A Nederhof, Mark-Jan
%A Satta, Giorgio
%A Shieber, Stuart
%S Proceedings of the Eighth International Conference on Parsing Technologies
%D 2003
%8 April
%C Nancy, France
%F nederhof-etal-2003-partially
%X 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.
%U https://aclanthology.org/W03-3020
%P 171-182

Markdown (Informal)

[Partially Ordered Multiset Context-free Grammars and Free-word-order Parsing](https://aclanthology.org/W03-3020) (Nederhof et al., IWPT 2003)

• Partially Ordered Multiset Context-free Grammars and Free-word-order Parsing (Nederhof et al., IWPT 2003)

ACL

• Mark-Jan Nederhof, Giorgio Satta, and Stuart Shieber. 2003. Partially Ordered Multiset Context-free Grammars and Free-word-order Parsing. In Proceedings of the Eighth International Conference on Parsing Technologies, pages 171–182, Nancy, France.