Kaplan, Ronald M. & Wedekind, Jürgen: Conservation and proper anchoring

Recognition/parsing, realization/generation, emptiness, and many more specific decision problems are known to be unsolvable for grammars in the unrestricted LFG formalism. In the general case, for example, it is not possible to decide whether a given string belongs to the language of an arbitrary LFG grammar or whether there is a string that expresses the grammatical relations of a given f-structure. This is because for a given input there are in principle no finite bounds on the number or sizes of derivations that must be inspected to answer even very basic questions. Kaplan and Bresnan (1982) addressed this issue in the earliest formulation of the LFG architecture by removing from linguistic consideration all derivations with c-structures that include recursive nonbranching dominance chains. This makes the parsing problem decidable because it bounds the size of a derivation by the length of the input string. But as was subsequently noticed, the NPD convention is too strong in that it proscribes certain kinds of linguistically desirable derivations, but also too weak because the generation problem remains undecidable even in the absence of NBD derivations. In this talk and in Kaplan and Wedekind (to appear) we introduce the Principle of Conservation as a pretheoretic restriction on language as a medium of communication: the derivational machinery that maps between sentences and their meanings may not add or subtract arbitrary amounts of information. We instantiate this principle in the LFG formalism by requiring the c-structures of all linguistically-relevant derivations to have specific anchors in both the string and the f-structure. The effect is that the height of a properly anchored c-structure is bounded by functions of the length of the string and the size of the f-structure, and thus that the parsing and generation problems are now both decidable.

Kaplan, Ronald M. and Jürgen Wedekind (to appear). Formal and computational properties of LFG. In Mary Dalrymple (ed.), Handbook of Lexical Functional Grammar. Language Science Press.

---

April 25, 2022