{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,18]],"date-time":"2026-04-18T09:57:33Z","timestamp":1776506253242,"version":"3.51.2"},"reference-count":47,"publisher":"MIT Press - Journals","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Computational Linguistics"],"published-print":{"date-parts":[[2020,11]]},"abstract":"<jats:p> The formalism for Lexical-Functional Grammar (LFG) was introduced in the 1980s as one of the first constraint-based grammatical formalisms for natural language. It has led to substantial contributions to the linguistic literature and to the construction of large-scale descriptions of particular languages. Investigations of its mathematical properties have shown that, without further restrictions, the recognition, emptiness, and generation problems are undecidable, and that they are intractable in the worst case even with commonly applied restrictions. However, grammars of real languages appear not to invoke the full expressive power of the formalism, as indicated by the fact that algorithms and implementations for recognition and generation have been developed that run\u2014even for broad-coverage grammars\u2014in typically polynomial time. This article formalizes some restrictions on the notation and its interpretation that are compatible with conventions and principles that have been implicit or informally stated in linguistic theory. We show that LFG grammars that respect these restrictions, while still suitable for the description of natural languages, are equivalent to linear context-free rewriting systems and allow for tractable computation. <\/jats:p>","DOI":"10.1162\/coli_a_00384","type":"journal-article","created":{"date-parts":[[2020,7,16]],"date-time":"2020-07-16T19:36:46Z","timestamp":1594928206000},"page":"515-569","source":"Crossref","is-referenced-by-count":3,"title":["Tractable Lexical-Functional Grammar"],"prefix":"10.1162","volume":"46","author":[{"given":"J\u00fcrgen","family":"Wedekind","sequence":"first","affiliation":[{"name":"University of Copenhagen, Department of Nordic Studies and                         Linguistics."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ronald M.","family":"Kaplan","sequence":"additional","affiliation":[{"name":"Stanford University, Linguistics Department."}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"281","reference":[{"key":"bib1","first-page":"143","volume":"14","author":"Bar-Hillel Yehoshua","year":"1961","journal-title":"Zeitschrift f\u00fcr Phonetik, Sprachwissenschaft und Kommunikationsforschung"},{"key":"bib2","unstructured":"Becker,\n                                Tilman,                                 Owen Rambow, and                                 Michael Niv. 1992.                         The derivational power of formal systems, or scrambling is                         beyond LCFRS. Technical report IRCS                     92-38, Institute for Research in Cognitive Science,                         University of Pennsylvania, Philadelphia,                         PA."},{"issue":"3","key":"bib3","first-page":"97","volume":"8","author":"Berwick Robert C.","year":"1982","journal-title":"American Journal of Computational Linguistics"},{"key":"bib4","doi-asserted-by":"publisher","DOI":"10.3115\/976744.976749"},{"key":"bib5","doi-asserted-by":"publisher","DOI":"10.3115\/977035.977044"},{"key":"bib6","first-page":"53","volume-title":"Proceedings of the 6th International Workshop on Parsing Technologies","author":"Boullier Pierre","year":"2000"},{"key":"bib7","first-page":"282","volume-title":"The Mental Representation of Grammatical Relations","author":"Bresnan Joan","year":"1982"},{"key":"bib8","volume-title":"Formal Issues in Lexical-Functional Grammar","author":"Bresnan Joan","year":"1995"},{"key":"bib9","volume-title":"Lexical-Functional Syntax","author":"Bresnan Joan","year":"2001"},{"issue":"4","key":"bib10","first-page":"613","volume":"13","author":"Bresnan Joan","year":"1982","journal-title":"Linguistic Inquiry"},{"key":"bib11","unstructured":"Crouch,\n                                Richard,                                 Mary,\n                                Dalrymple,                                 Ronald M. Kaplan, Tracy\n                                Holloway King, John\n                                T. Maxwell III, and                                 Paula Newman.                         2008. XLE documentation.                         Technical report, Palo Alto Research                         Center, Palo Alto, CA.                         Available at http:\/\/www2.parc.com\/isl\/groups\/nltt\/xle\/doc\/xle_toc.html."},{"key":"bib12","doi-asserted-by":"publisher","DOI":"10.1163\/9781849500104"},{"key":"bib13","volume-title":"Formal Issues in Lexical-Functional Grammar","author":"Dalrymple Mary","year":"1995"},{"key":"bib14","first-page":"131","author":"Dalrymple Mary","year":"1995","journal-title":"Formal Issues in Lexical-Functional Grammar"},{"issue":"2","key":"bib15","doi-asserted-by":"crossref","first-page":"377","DOI":"10.15398\/jlm.v3i2.82","volume":"3","author":"Dalrymple Mary","year":"2015","journal-title":"Journal of Language Modelling"},{"key":"bib16","doi-asserted-by":"publisher","DOI":"10.1007\/s10849-008-9062-9"},{"key":"bib17","doi-asserted-by":"publisher","DOI":"10.1007\/s10849-005-4511-1"},{"key":"bib18","volume-title":"Attribute\u2013Value Logic and the Theory of Grammar","author":"Johnson Mark","year":"1988"},{"key":"bib19","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511597855.007"},{"key":"bib20","doi-asserted-by":"publisher","DOI":"10.1007\/s11168-011-9081-6"},{"key":"bib21","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-14846-0"},{"key":"bib22","doi-asserted-by":"publisher","DOI":"10.1002\/lnc3.359"},{"key":"bib23","first-page":"7","volume-title":"Formal Issues in Lexical-Functional Grammar","author":"Kaplan Ronald M","year":"1995"},{"key":"bib24","first-page":"173","volume-title":"The Mental Representation of Grammatical Relations","author":"Kaplan Ronald M.","year":"1982"},{"key":"bib25","doi-asserted-by":"publisher","DOI":"10.3115\/991635.991695"},{"key":"bib26","doi-asserted-by":"publisher","DOI":"10.3115\/991635.991696"},{"key":"bib27","unstructured":"Kaplan, Ronald\n                                M. and John\n                                T. Maxwell III. 1996.                         LFG grammar writer\u2019s workbench.                         Technical report, Xerox Palo Alto                         Research Center, Palo Alto,                         CA. Available at ftp:\/\/ftp.parc.xerox.com\/pub\/lfg\/lfgmanual.ps."},{"key":"bib28","first-page":"130","volume-title":"Proceedings of the International Lexical-Functional Grammar Conference 2019","author":"Kaplan Ronald M.","year":"2019"},{"key":"bib29","first-page":"17","author":"Kaplan Ronald M.","year":"1989","journal-title":"Alternative Conceptions of Phrase Structure"},{"key":"bib30","doi-asserted-by":"publisher","DOI":"10.1007\/s11168-005-1295-z"},{"key":"bib31","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8640.1994.tb00011.x"},{"key":"bib32","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-3986-5_12"},{"key":"bib33","volume-title":"Proceedings of the International Lexical-Functional Grammar Conference 1996","author":"Maxwell John T.","year":"1996"},{"key":"bib34","doi-asserted-by":"publisher","DOI":"10.1145\/322186.322198"},{"issue":"1","key":"bib35","first-page":"119","volume":"27","author":"Nishino Tetsuro","year":"1991","journal-title":"Language Research"},{"key":"bib36","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/ext013"},{"key":"bib37","first-page":"138","volume-title":"Proceedings of the 5th Meeting on Mathematics of Language","author":"Rambow Owen","year":"1997"},{"issue":"3","key":"bib38","first-page":"530","volume":"18","author":"Ristad Eric S","year":"1987","journal-title":"Linguistic Inquiry"},{"key":"bib40","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(91)90374-B"},{"key":"bib41","doi-asserted-by":"publisher","DOI":"10.3115\/981574.981592"},{"key":"bib42","doi-asserted-by":"publisher","DOI":"10.1016\/S0049-237X(08)71125-X"},{"key":"bib43","doi-asserted-by":"publisher","DOI":"10.3115\/981175.981190"},{"issue":"2","key":"bib44","first-page":"277","volume":"25","author":"Wedekind J\u00fcrgen","year":"1999","journal-title":"Computational Linguistics"},{"key":"bib45","doi-asserted-by":"publisher","DOI":"10.1162\/COLI_a_00191"},{"key":"bib46","doi-asserted-by":"publisher","DOI":"10.1162\/COLI_a_00113"},{"key":"bib47","unstructured":"Weir, David\n                                J. 1988. Characterizing mildly context-sensitive                         grammar formalisms. Ph.D. thesis,                         University of Pennsylvania,                         Philadelphia, PA."},{"key":"bib48","first-page":"215","author":"Zaenen Annie","year":"1995","journal-title":"Formal Issues in Lexical-Functional Grammar"}],"container-title":["Computational Linguistics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mitpressjournals.org\/doi\/pdf\/10.1162\/coli_a_00384","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,12]],"date-time":"2021-03-12T21:28:35Z","timestamp":1615584515000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/coli\/article\/46\/3\/515-569\/93379"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11]]},"references-count":47,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,11]]}},"alternative-id":["10.1162\/coli_a_00384"],"URL":"https:\/\/doi.org\/10.1162\/coli_a_00384","relation":{},"ISSN":["0891-2017","1530-9312"],"issn-type":[{"value":"0891-2017","type":"print"},{"value":"1530-9312","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,11]]}}}