Tractable Lexical-Functional Grammar

Jürgen Wedekind; Ronald M. Kaplan

Tractable Lexical-Functional Grammar

Jürgen Wedekind, Ronald M. Kaplan

Department of Nordic Studies and Linguistics

Abstract

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.

Original language	English
Journal	Computational Linguistics
Number of pages	50
ISSN	1530-9312
Publication status	Submitted - 21 Dec 2018

Cite this

@article{620b3c2390774ec4b8331a466c5c8235,

title = "Tractable Lexical-Functional Grammar",

abstract = "The formalism for Lexical-Functional Grammar (LFG) was introduced in the 1980{\textquoteright}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, withoutfurther 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 thatrun 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 linearcontext-free rewriting systems and allow for tractable computation.",

author = "J{\"u}rgen Wedekind and Kaplan, {Ronald M.}",

year = "2018",

month = dec,

day = "21",

language = "English",

journal = "Computational Linguistics",

issn = "1530-9312",

publisher = "MIT Press",

}

TY - JOUR

T1 - Tractable Lexical-Functional Grammar

AU - Wedekind, Jürgen

AU - Kaplan, Ronald M.

PY - 2018/12/21

Y1 - 2018/12/21

N2 - 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, withoutfurther 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 thatrun 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 linearcontext-free rewriting systems and allow for tractable computation.

AB - 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, withoutfurther 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 thatrun 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 linearcontext-free rewriting systems and allow for tractable computation.

M3 - Journal article

SN - 1530-9312

JO - Computational Linguistics

JF - Computational Linguistics

ER -