Reversibility

Intuitively, we call a program `reversible' if it is capable of both
parsing and generation on the basis of a single
characterization of the relation between semantic structures and
phonological structures.
The following definitions of *reversibility* are meant to be
independent of the way we go about achieving a reversible natural
language processing component. Furthermore, the definitions abstract
away from the actual representations between which we are defining
relations. In chapter 5 we propose to use
constraint-based grammars for a transfer component of an MT system. In
that case the relation defined by the grammar is between semantic
representations of different languages; the following definitions are
generalized in order to be applicable for such usages as well.

A program or system will be called * r-reversible* iff it
computes a binary relation

{*x*|}

- A program
*P*isiff*r*-reversible*P*computes*r*in both directions. - A relation
*r*is*reversible*iff there exists an*r*-reversible program.

Consider the case where *r* is the relation between
phonological and semantic representations defined by some grammar. In
this case a program is said to compute this relation in both
directions (i.e. the program is reversible w.r.t. this relation) iff
for a given phonological representation the program returns the
corresponding semantic representation; for a given semantic
representation the program returns the corresponding phonological
representations. Such a program may consist of a parser and
a generator (depending on the value of *dir*), or alternatively the
program consists of a single uniform algorithm. For example in the
case of the meta-interpreter for
()-grammars to be presented in
chapter 2, the value of *dir* defines to which path (eg.
*phon* or
*sem*) the input has to be assigned, otherwise
the parser and generator are equivalent.

Systems in which the relation between phonological and semantic
representations is defined procedurally are seldom reversible in this
respect, because it is very difficult to make sure that the program
indeed computes the same relation in both directions. On the other
hand, a system based on a single *declarative grammar* necessarily
is reversible.

Arguably, the above defined notion of reversibility is somewhat weak.
According to the definition above, any recursively enumerable relation
is reversible. However, in practice it is often the case that a
grammar that is developed from a single perspective (eg. parsing
perspective) is completely useless in the other direction because it
simply fails to terminate in all interesting cases (let alone
efficiency considerations). Therefore, I define what it means for a
relation to be *effectively reversible*. A relation is effectively
reversible if it can be effectively computed in both directions, i.e.
there exists a program computing the relation in both directions, and
furthermore the program always halts. In the terminology of
[33], we require that there exists an *algorithm* computing the relation.

- A program
*P*is effectively*r*-reversible iff*P*is*r*-reversible; and*P*is guaranteed to terminate (for every input).

- A relation
*r*is*effectively reversible*iff there exists an effectively*r*-reversible program.

If I use the term *reversible* in the remainder of this thesis,
then I will invariably mean *effectively reversible*.

Next I show that the composition of (effectively) reversible relations is (effectively) reversible. This proposition motivates the use of a series of grammars, each defining an (effectively) reversible relation, to obtain an (effectively) reversible MT system (chapter 5).

1998-09-30