I will call a binary relation
*reversible*
if the relation is *symmetric* and *computable*. Both symmetry and computability
will be explained in the following subsections.
A grammar is reversible for a relation iff is reversible and defined by .
For example, a grammar that relates strings to logical forms is reversible if both the parsing
and generation problem is computable, and the relation between strings and
logical forms is symmetric; the parsing problem is computable if for a given string
all corresponding logical forms can be enumerated by some terminating procedure;
such a procedure should halt if the given string does not have a corresponding
logical form.
Thus: reversible = symmetric + computable. Note that reversibility as defined here
is different from bidirectionality. The latter merely says that grammars are to be
used in two directions, but does not state how the two directions relate.

It is easy to see that a composition of reversible relations is a a reversible relation too; i.e. if some feature structure is related to some feature structure via the reversible relations , each defined by some reversible grammar , then is reversible. Thus an MT system that defines a relation via the relations , and is reversible if are reversible.

Fri Nov 25 13:42:02 MET 1994