|
|
|
|
|
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 . 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,
mention that the equivalence problem with only the axioms of commutativity
and associativity for their `Indexed Language' has factorial complexity. [83 <node102.html>]
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 Another point raised by [83
<node102.html>] 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 <node102.html>,94 <node102.html>]. This definition of
the generation problem will be used throughout this thesis as well, and made
precise in chapter <node15.html>.
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 <node15.html>,
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
<node102.html>], 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 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. |
(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. 
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.