Some Remarks on the Decidability of the Generation Problem in LFG- and PATR-Style Unification Grammars

Some Remarks on the Decidability of the Generation Problem in LFG- and PATR-Style Unification Grammars Jiirgen Wedekind Institute for Natural Language Processing University of Stuttgart Azenbergstr. 12 D-70174 Stuttgart, FRG juergen@ims.uni-stuttgart.de Abstract 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. 1 Introduction Unification Grammars with a context-free skeleton, like Lexical Fhnctional Grammar (LFG) and PATR- II (cf. e.g. Kaplan and Bresnan 1982, Shieber et al. 1983) assign to a sentence not only a constituent structure (c-structure), but also an additional lin- guistic entity. In the rather restricted grammars of the early stage this entity is identified with a special graph structure, commonly called feature structure. Since a string is regarded as well-formed only if a (well-formed) feature structure is assigned to it by the grammar, two inverse decidability problems arise which had to be solved in order to know whether we can formulate terminating parsing and generation al- gorithms. If we retain the terminology of the early stages then an adequate parsing algorithm requires that we can decide for a given grammar and a given string whether there exists a feature structure as- signed to it by the grammar (parsing problem) and an adequate generation algorithm requires that we can decide for a given grammar and a given feature structure whether there exists a sentence to which this structure is assigned by the grammar (genera- tion problem). While we already know for a long time that the parsing problem is undecidable (cf. Kaplan and Bres- nan 1982, Johnson 1988), we want to show in this pa- per that the generation problem is decidable even for unrestricted (not off-line parsable) unification gram- mars. For the proof we first introduce in section 2 the type of grammar we want to consider. In section 3 we then define the generation problem and show its decidability in two steps. 2 Preliminaries The unification grammars we want to consider con- sist of rules with a context-free skeleton and a set of annotations associated with the constituents men- tioned in the rules. Typical examples taken from LFG and PATR-II are given in figure 1. For the for- S --~ NP VP S --+ NP VP (t SUB J) ----$ j'=$ (VP AGR) = (NP AGR) NP -+ John NP -4 Uther (1" PRED) = JOHN (NP AGR NUM) = SG (NP AGR PER) ---- 3RD Figure 1 Examples of …

Content truncated to 500 words