Quarterly (March, June, September, December)
160 pp. per issue
6 3/4 x 10
2014 Impact factor:

Computational Linguistics

Paola Merlo, Editor
September 2014, Vol. 40, No. 3, Pages 533-538
(doi: 10.1162/COLI_a_00191)
@ 2014 Association for Computational Linguistics
On the Universal Generation Problem for Unification Grammars
Article PDF (128.71 KB)

The universal generation problem for unification grammars is the problem of determining whether a given grammar derives any terminal string with a given feature structure. It is known that the problem is decidable for LFG and PATR grammars if only acyclic feature structures are taken into consideration. In this brief note, we show that the problem is undecidable for cyclic structures. This holds even for grammars that are off-line parsable.