Some remarks on the decidability of the generation problem in LFG- and PATR-style unification grammars
Jürgen Wedekind · 1995
In this paper, we prove the decidability of the generation problem for those unification 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 input is always restricted to derivations whose length is limited by some fixed upper bound which is determined relative to the "size" of the input.