Reversible transfer

The formalism also allows transfer grammars that define transfer
relations that are not reversible, as is clear from the
proof in section 2.5. The objective, though,
is to build an *reversible* machine translation system.
In this section I will define a simple
condition on transfer rules such that a top-down interpreter is guaranteed to
terminate for grammars of which the rules satisfy the condition.

The constraint I am about to propose embodies the hypothesis that translation is defined compositionally; i.e. the translation of some structure is defined in terms of the translations of the parts of that structure. In section 5.6 I show that certain types of non-compositional translation can still be handled by a reversible transfer grammar. Therefore I argue that the constraint to be proposed embodies an interesting compromise between expressive power and computability.

Assume the transfer rules define a relation between the paths *p* and
*q*. I will require that for each rule the value of *p* of the mother
node is strictly larger than the value of *p* of each of the daughters,
and similarly, the value of *q* of the mother node is strictly larger
than the value of *q* of the mother. I define these sizes in terms of
the underlying feature graph models. The size of a feature graph simply
is defined as the number of nodes of the graph.
For a rule

I require that for all assignments
, and all
*j*,
1
*j*
*n*,

The most straightforward way to satisfy this condition is for a mother
node to share proper parts of its *p* and *q* values with the *p* and
*q* values of each of its daughters (making the simplifying assumption
that semantic structures are not cyclic). For example, all of the
rules given so far satisfy the condition by sharing sub-parts of the
value of the
*gb* and
*nl* attribute. A rule such as the
following would fail to meet the condition:

To see that this rule violates the condition, consider the assignment
which assigns both *X* and *Y* to a graph whose subgraph at
path *p* is the graph

Another way to understand this, is to see that the feature structure
associated with the daughter node, in fact unifies with the feature
structure associated with the mother node. Thus, even though the
daughter node does not `mention' the
*pred* attribute, this does
not mean that there cannot be a value for this attribute. The rules in
the previous sections of this chapter all satisfy the condition, as in
these rules the daughter nodes are associated with proper sub-parts of
the feature structure associated with the mother node.

A top-down interpreter for transfer grammars can be defined as the meta-interpreter defined in chapter 2, repeated here for convenience in figure 5.6.

This algorithm thus simply performs a top-down expansion of the input sign. By the size condition we know however that each recursive call constitutes a smaller problem and hence transfer will terminate, given that the ordering on sizes is well-founded. Given the equivalence condition on the

1998-09-30