@article{wedekind-kaplan-2021-lfg,
title = "{LFG} Generation from Acyclic {F}-Structures is {NP}-Hard",
author = {Wedekind, J{\"u}rgen and
Kaplan, Ronald M.},
journal = "Computational Linguistics",
volume = "47",
number = "4",
month = dec,
year = "2021",
address = "Cambridge, MA",
publisher = "MIT Press",
url = "https://aclanthology.org/2021.cl-4.31",
doi = "10.1162/coli_a_00419",
pages = "939--946",
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.",
}
<?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)
ACL