It is known that unrestricted unification or constraint-based grammars have the formal power of a Turing machine (e.g., [Pereira and Warren1983], [Haas1989]), thus termination can only be guaranteed for restricted classes of grammar formalisms. For example in section 4.12 we have shown that the subcategorization rule can cause non-termination through completion if we do not restrict the applicability of the empty vp-rule.
From the work of [Bresnan1982], [Pereira and Warren1983], [Haas1989], and
[Shieber1989] we know that termination can be guaranteed if a grammar
is off-line parsable, i.e., if it is finitely ambiguous.
These results, however, have only been worked out for the case of
parsing. A termination condition for both parsing and generation is given
in [Dymetman et al.
1990] for the class of ``Lexical Grammars''. It states that
if each rule or lexical entry consumes a non-empty part of the input
(either string or semantic expression) then termination can be
guaranteed.
For the case of generation, for example, this means that termination is ensured
for grammars in which the lexical entries are defined in such a way, that the
semantic structures of each of the elements on the subcategorization list is
``smaller'' than the semantic structures of the lexical entry itself (see
also [VanNoord1993]). If a grammar fulfills these criterions our
uniform algorithm is guaranteed to terminate.