{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,4]],"date-time":"2022-04-04T02:15:12Z","timestamp":1649038512448},"reference-count":8,"publisher":"MIT Press - Journals","issue":"4","license":[{"start":{"date-parts":[[2021,8,13]],"date-time":"2021-08-13T00:00:00Z","timestamp":1628812800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0\/"}],"content-domain":{"domain":["direct.mit.edu"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,12,23]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>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.<\/jats:p>","DOI":"10.1162\/coli_a_00419","type":"journal-article","created":{"date-parts":[[2021,8,13]],"date-time":"2021-08-13T14:46:16Z","timestamp":1628865976000},"page":"939-946","update-policy":"http:\/\/dx.doi.org\/10.1162\/mitpressjournals.corrections.policy","source":"Crossref","is-referenced-by-count":0,"title":["LFG Generation from Acyclic F-Structures is NP-Hard"],"prefix":"10.1162","volume":"47","author":[{"given":"J\u00fcrgen","family":"Wedekind","sequence":"first","affiliation":[{"name":"University of Copenhagen, Department of Nordic Studies and Linguistics. jwedekind@hum.ku.dk"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ronald M.","family":"Kaplan","sequence":"additional","affiliation":[{"name":"Stanford University, Linguistics Department. rmkaplan@stanford.edu"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"281","published-online":{"date-parts":[[2021,12,23]]},"reference":[{"issue":"2","key":"2022010319054898500_bib1","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/0020-0190(94)00084-0","article-title":"A term equality problem equivalent to graph isomorphism","volume":"51","author":"Basin","year":"1994","journal-title":"Information Processing Letters"},{"issue":"3\u20134","key":"2022010319054898500_bib2","first-page":"97","article-title":"Computational complexity and Lexical-Functional Grammar","volume":"8","author":"Berwick","year":"1982","journal-title":"American Journal of Computational Linguistics"},{"key":"2022010319054898500_bib3","first-page":"173","article-title":"Lexical-Functional Grammar: A formal system for grammatical representation","volume-title":"The Mental Representation of Grammatical Relations","author":"Kaplan","year":"1982"},{"key":"2022010319054898500_bib4","first-page":"130","article-title":"Tractability and discontinuity","volume-title":"Proceedings of the International Lexical-Functional Grammar Conference 2019","author":"Kaplan","year":"2019"},{"issue":"1","key":"2022010319054898500_bib5","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1016\/0166-218X(84)90081-7","article-title":"A simplified NP-complete satisfiability problem","volume":"8","author":"Tovey","year":"1982","journal-title":"Discrete Applied Mathematics"},{"issue":"3","key":"2022010319054898500_bib6","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1162\/COLI_a_00191","article-title":"On the universal generation problem for unification grammars","volume":"40","author":"Wedekind","year":"2014","journal-title":"Computational Linguistics"},{"issue":"4","key":"2022010319054898500_bib7","doi-asserted-by":"publisher","first-page":"867","DOI":"10.1162\/COLI_a_00113","article-title":"LFG generation by grammar specialization","volume":"38","author":"Wedekind","year":"2012","journal-title":"Computational Linguistics"},{"issue":"3","key":"2022010319054898500_bib8","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1162\/coli_a_00384","article-title":"Tractable Lexical-Functional Grammar","volume":"46","author":"Wedekind","year":"2020","journal-title":"Computational Linguistics"}],"container-title":["Computational Linguistics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/direct.mit.edu\/coli\/article-pdf\/47\/4\/939\/1979812\/coli_a_00419.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/direct.mit.edu\/coli\/article-pdf\/47\/4\/939\/1979812\/coli_a_00419.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,1,3]],"date-time":"2022-01-03T19:05:57Z","timestamp":1641236757000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/coli\/article\/47\/4\/939\/106929\/LFG-Generation-from-Acyclic-F-Structures-is-NP"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,12]]},"references-count":8,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2021,12,23]]},"published-print":{"date-parts":[[2021,12,23]]}},"URL":"https:\/\/doi.org\/10.1162\/coli_a_00419","relation":{},"ISSN":["0891-2017","1530-9312"],"issn-type":[{"value":"0891-2017","type":"print"},{"value":"1530-9312","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2021,12]]},"published":{"date-parts":[[2021,12]]}}}