@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://preview.aclanthology.org/jlcl-multiple-ingestion/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."
}