Paper: LFG Generation Produces Context-Free Languages

ACL ID C00-1062
Title LFG Generation Produces Context-Free Languages
Venue International Conference on Computational Linguistics
Session Main Conference
Year 2000

This pat}er examines the generation prol}lem for a ce]:tain linguisti:ally relevant sul0class of LFG gram- mars. Our main result; is that the set of strings that such a grammar relates to a particular f-structure is a context-free language. This result obviously ex- l;enls to other {:ontext-free basel grammatical f(}r- malisIns, such its PATll,, and also to formalisms {,hal; 1)ermit a context-free skeleton to 1}e extracted (1)er- haps some variants {}f HPSG). The l)]:(}{)f is cmstru:- l;ive: from the given f-sl;ru:ture a l)art;i:ular c}ntext- free grannnar is create, d whose, yMl is the (lesire, d sel; Of S|;l'illgS. ~4aily existing generation sl;ral;e, gies (top-{lown, l}ottom-ul}, head-driven) can be under- stood as all:ernative ways of avoiding the creation of useless context-Dee produc...