Tractable Lexical-Functional Grammar

Publikation: Bidrag til tidsskriftTidsskriftartikelfagfællebedømt

  • Jürgen Wedekind
  • Ronald M. Kaplan
The formalism for Lexical-Functional Grammar (LFG) was introduced in the 1980’s 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, real grammars of real languages appear not to invoke the full expressive power of the formalism, and algorithms and implementations for recognition and generation have been developed that
run in typically polynomial time. This paper formalizes some limitations 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.
OriginalsprogEngelsk
TidsskriftComputational Linguistics
Vol/bind46
Udgave nummer3
Sider (fra-til)515-569
Antal sider55
ISSN1530-9312
StatusUdgivet - sep. 2020

ID: 210200397