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.