next up previous
Next: Computability Up: Reversibility Previous: Reversibility


A relation is symmetric iff implies where and are equivalent. For an MT system we want to define `equivalence' in such a way that the translation relation is a symmetric relation between strings. However, strings are feature structures thus we must define equivalence for feature structures to obtain this effect.

Unification grammars as they are commonly used implement a rather weak notion of equivalence between feature structures: feature structures and are equivalent if they can unify:

If feature structures are taken to stand for all their ground instances this yields an acceptable version of symmetry. Moreover, under the assumption that feature structures which represent strings are always ground (i.e. these feature structures cannot be extended), this results in a symmetric relation between (feature structures that represent) strings.

It is also possible to define a `strong' notion of equivalence for feature structures that does not rely on this assumption.


A grammar that defines a computable relation between two attributes under the strong definition of equivalence might be called strongly reversible. Similarly a weakly reversible grammar is reversible under a weak definition of equivalence. Again these results can be generalized to a series of unification grammars. The strong version of equivalence can be motivated on the ground that it may be easier to obtain computability; this is the topic of the next subsection. In section 3.2 I will discuss possible relaxations of the strong version of equivalence to obtain `mildly' reversible grammars.

Gertjan van Noord
Fri Nov 25 13:42:02 MET 1994