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.

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.

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, we 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
[Hopcroft and Ullman1979], 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 we use the term *reversible* in the remainder of this article,
then we will invariably mean *effectively reversible*.

1998-09-30