Paper: Some Remarks On The Decidability Of The Generation Problem In LFG- And PATR-Style Unification Grammars

ACL ID E95-1007
Title Some Remarks On The Decidability Of The Generation Problem In LFG- And PATR-Style Unification Grammars
Venue Annual Meeting of The European Chapter of The Association of Computational Linguistics
Session Main Conference
Year 1995
Authors

In this paper, we prove the decidability of the generation problem for those unifica- tion grammars which are based on context- free phrase structure rule skeletons, like e.g. LFG and PATR-II. The result shows a perhaps unexpected asymmetry, since it is valid also for those unification grammars whose parsing problem is undecidable, e.g. grammars which do not satisfy the off-line parsability constraint. The general proof is achieved by showing that the space of the derivations which have to be considered in order to decide the problem for a given in- put is always restricted to derivations whose length is limited by some fixed upper bound which is determined relative to the "size" of the input.