However, in the general case one cannot expect from a generation system, that it is indeed capable of producing an answer in the previous example. The problem whether two expressions are logically equivalent is undecidable for any `interesting' logic. Therefore, it is not to be expected that it is possible to devise a serious logic for natural language semantics, in which logical equivalence is decidable.

Furthermore, even simple kinds of equivalences may give rise to an enormous increase of computational complexity. For example, [12] mention that the equivalence problem with only the axioms of commutativity and associativity for their `Indexed Language' has factorial complexity.

[83] mentions that, from the standpoint of natural
language generation, ``the class of equivalent logical forms [...] is not
really closed under logical equivalence''. He claims that a
finer-grained notion of *intentional equivalence* is required,
such that for example *p* and
*p*
(*q*
*q*) would not
necessarily be intentionally equivalent; and these formulas might
correspond to different utterances, one about *p* only, the other
about *p* and *q*. Clearly it depends on the actual logic
whether or not a different form of equivalence is called for.
It may also be the case that in an appropriate natural language
semantics those two formulas are not logically equivalent anyway.

Another point raised by [83] is that even for logics in which each formula has a (unique) canonical form, a problem remains unless these canonical forms correspond exactly to those derived by the natural language grammar. Shieber mentions:

We might use a logic in which logical equivalence classes of expressions are all trivial, that is, any two distinct expressions mean something different. In such a logic, there are no artifactual syntactic remnants in the syntax of the logical language. Furthermore, expressions of the logic must be relatable to expressions of the natural language with a reversible grammar. Alternatively, we could use a logic for which canonical forms, corresponding exactly to the natural language grammar's logical forms, do exist.

The difference between the two approaches is only an apparent one, for in the latter case the equivalence classes of logical forms can be identified as logical forms of a new logical language with no artifactual distinctions. Thus, the second case reduces to the first. The central problem in either case, then, is discovery of a logical language which exactly and uniquely represents all the meaning distinctions of natural language utterances and no others. This holy grail, of course, is just the goal of knowledge representation for natural language in general; we are unlikely to be able to rely on a full solution soon.

For the reasons mentioned above, we cannot expect the generator in the
previous example to produce *u'* in the general case. Indeed, the
generation systems that have been proposed all impose a stronger
condition on the generation task. Not only is the generator required
to produce an utterance which is assigned an equivalent logical form
by the grammar, but, moreover, the `syntax' of the logical form must
be the same as well. For a theoretical perspective on this, cf.
[95,94]. This definition of the
generation problem will be used throughout this thesis as well, and
made precise in chapter 2.

Clearly, this is a somewhat disappointing result. Even though the problem of logical equivalence in general is undecidable, it may be the case that we can devise techniques which solve at least part of the problem; i.e. are able to recognize certain equivalences. I believe that the techniques developed in the remainder of this thesis can be augmented with such techniques once these become available, as follows. In a constraint-based grammar logical forms are defined by constraints. In the constraint-language to be defined in chapter 2, the only equivalence relation is the one we obtain by the equality of our constraint language. However, the general way in which I define a constraint-based formalism, along the lines of [32], allows for more powerful constraints, if appropriate constraint-solving mechanisms are available.

The principal way to enrich the equivalence notion in a
constraint-based formalism is to enrich the constraint-language. Thus,
if we take
*p*
*q* to be equivalent to
*q*
*p*, then we
should add some axioms to the constraint language to this effect. The
result of this approach will then be that *p*
*q* will `unify'
with
*q*
*p*. Note that the parsing- and generation algorithms
defined in this thesis can be viewed as abstracting away from the
particular constraint-language that is being used. Thus, given
appropriate constraint-solving techniques (unification algorithms),
more powerful constraints can easily be imported.

The point then is, that even though we have not much to say about the logical equivalence problem, we argue that the results of this thesis are not dependent on the way in which this problem is solved eventually. This is so, because on the one hand we abstract away from the actual choice of semantic representations, and on the other hand provide for a hook in which equivalences can be defined (in the constraint-language); the techniques developed in this thesis can easily be adapted to more powerful constraint-languages as well.

1998-09-30