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. In chapter 5 we propose to use constraint-based grammars for a transfer component of an MT system. In that case the relation defined by the grammar is between semantic representations of different languages; the following definitions are generalized in order to be applicable for such usages as well.

A program or system will be called r-reversible iff it computes a binary relation r in both directions. The idea is that, given an element of a pair in the relation, the program computes the corresponding element(s) of that pair. To encode the `direction' of the relation I assume that the input for the program consists of a pair $\langle$dir, x$\rangle$ where dir represents the direction which the program should compute. The value of dir is either 0 or 1. If the value is 0, then the program computes the relation from left to right; if the value is 1 then the program computes the relation from right to left. ^1.3

Definition 1 (Compute a relation in both directions)   A program P computes a relation r in both directions, iff P enumerates for a given input $\langle$dir, e$\rangle$ the set

{x|$$\begin{array}{l} \langle e,x \rangle \in r \wedge dir=0 ~\vee \\ \langle x,e \rangle \in r \wedge dir=1 \end{array}$$}

Definition 2 (Reversible)  

• A program P is r-reversible iff 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. For example in the case of the meta-interpreter for $\cal {R}$($\cal {L}$)-grammars to be presented in chapter 2, the value of dir defines to which path (eg. phon or sem) the input has to be assigned, otherwise the parser and generator are equivalent.

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, I 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 [33], we require that there exists an algorithm computing the relation.

Definition 3 (Effectively reversible)  

• 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 I use the term reversible in the remainder of this thesis, then I will invariably mean effectively reversible.

Next I show that the composition of (effectively) reversible relations is (effectively) reversible. This proposition motivates the use of a series of grammars, each defining an (effectively) reversible relation, to obtain an (effectively) reversible MT system (chapter 5).

Definition 4 (Composition)   The composition of two relations r₁or₂ is the relation {$\langle$a, c$\rangle$|$\langle$a, b$\rangle$ $\in$ r₁ and $\langle$b, c$\rangle$ $\in$ r₂}.

Proposition.

The composition of two effectively reversible relations is effectively reversible.

Proof.

Assume r and r' are reversible. We need to show that ror' is reversible. Let P and P' compute resp. r and r' in both directions. Construct the program as in figure 1.1 which computes the series of P and P', the order of which is dependent on the direction. Each element of the output of the first program is taken as the input to the second program. As both P and P' terminate, the two programs in series terminate too.

Figure 1.1: Program computing composition.

Another, intuitively more attractive way to think about the above construction is pictured in figure 1.2.

Figure 1.2: Series of reversible programs