Logical equivalence problem

It is not problematic to assume that feature structures can be used to represent semantic representations of any sort. However, it is problematic to assume that the constraint-language we define feature structures with, is rich enough to capture the intrinsic properties of the logic. The problem that arises in this context is called the logical equivalence problem [4]. A logic defines logical equivalences between formulas. If such equivalences are not taken into account by the grammatical formalism, unexpected results may occur. For example, consider a grammar that relates some utterance u with the meaning representation m. Suppose, furthermore, that in the logical language from which m is taken, m' is equivalent to m. What should happen if we ask a system based on that grammar to generate an utterance for the semantic structure m'? In the ideal case, the system should indeed produce u as a possible utterance. This is so, because the `form' of the formulas should not really matter; such formulas stand for a piece of meaning, and if two formulas describe the same piece of meaning then these two formulas should behave in the same way.

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 $\wedge$ (q $\vee$ $\neg$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 $\oplus$ q to be equivalent to q $\oplus$ p, then we should add some axioms to the constraint language to this effect. The result of this approach will then be that p $\oplus$ q will `unify' with q $\oplus$ 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.