<?xml version="1.0" encoding="UTF-8"?>
<modsCollection xmlns="http://www.loc.gov/mods/v3">
<mods ID="wedekind-kaplan-2021-lfg">
    <titleInfo>
        <title>LFG Generation from Acyclic F-Structures is NP-Hard</title>
    </titleInfo>
    <name type="personal">
        <namePart type="given">Jürgen</namePart>
        <namePart type="family">Wedekind</namePart>
        <role>
            <roleTerm authority="marcrelator" type="text">author</roleTerm>
        </role>
    </name>
    <name type="personal">
        <namePart type="given">Ronald</namePart>
        <namePart type="given">M</namePart>
        <namePart type="family">Kaplan</namePart>
        <role>
            <roleTerm authority="marcrelator" type="text">author</roleTerm>
        </role>
    </name>
    <originInfo>
        <dateIssued>2021-12</dateIssued>
    </originInfo>
    <typeOfResource>text</typeOfResource>
    <genre authority="bibutilsgt">journal article</genre>
    <relatedItem type="host">
        <titleInfo>
            <title>Computational Linguistics</title>
        </titleInfo>
        <originInfo>
            <issuance>continuing</issuance>
            <publisher>MIT Press</publisher>
            <place>
                <placeTerm type="text">Cambridge, MA</placeTerm>
            </place>
        </originInfo>
        <genre authority="marcgt">periodical</genre>
        <genre authority="bibutilsgt">academic journal</genre>
    </relatedItem>
    <abstract>The universal generation problem for LFG grammars is the problem of determining whether a given grammar derives any terminal string with a given f-structure. It is known that this problem is decidable for acyclic f-structures. In this brief note, we show that for those f-structures the problem is nonetheless intractable. This holds even for grammars that are off-line parsable.</abstract>
    <identifier type="citekey">wedekind-kaplan-2021-lfg</identifier>
    <identifier type="doi">10.1162/coli_a_00419</identifier>
    <location>
        <url>https://aclanthology.org/2021.cl-4.31</url>
    </location>
    <part>
        <date>2021-12</date>
        <detail type="volume"><number>47</number></detail>
        <detail type="issue"><number>4</number></detail>
        <extent unit="page">
            <start>939</start>
            <end>946</end>
        </extent>
    </part>
</mods>
</modsCollection>

%0 Journal Article
%T LFG Generation from Acyclic F-Structures is NP-Hard
%A Wedekind, Jürgen
%A Kaplan, Ronald M.
%J Computational Linguistics
%D 2021
%8 December
%V 47
%N 4
%I MIT Press
%C Cambridge, MA
%F wedekind-kaplan-2021-lfg
%X The universal generation problem for LFG grammars is the problem of determining whether a given grammar derives any terminal string with a given f-structure. It is known that this problem is decidable for acyclic f-structures. In this brief note, we show that for those f-structures the problem is nonetheless intractable. This holds even for grammars that are off-line parsable.
%R 10.1162/coli_a_00419
%U https://aclanthology.org/2021.cl-4.31
%U https://doi.org/10.1162/coli_a_00419
%P 939-946

Markdown (Informal)

[LFG Generation from Acyclic F-Structures is NP-Hard](https://aclanthology.org/2021.cl-4.31) (Wedekind & Kaplan, CL 2021)

• LFG Generation from Acyclic F-Structures is NP-Hard (Wedekind & Kaplan, CL 2021)

ACL

• Jürgen Wedekind and Ronald M. Kaplan. 2021. LFG Generation from Acyclic F-Structures is NP-Hard. Computational Linguistics, 47(4):939–946.