4 Lenient composition

The necessary operation, let us call it lenient composition, is not difficult to construct, but to our knowledge it has not previously been defined. Frank and Satta [7] come very close but do not take the final step to encapsulate the notion. Hammond [8] has the idea but lacks the means to spell it out in formal terms.

As the first step toward defining lenient composition, let us review an old notion called priority union (Kaplan [12]). This term was originally defined as an operation for unifying two feature structures in a way that eliminates any risk of failure by stipulating that one of the two has priority in case of a conflict. A finite-state version of this notion has proved very useful in the management of transducer lexicons (Kaplan and Newman [11]).

 

Figure 10:   Example of priority union.

Let us consider the relations Q and R depicted in Figure 10. The Q relation maps a to x and b to y. The R relation maps b to z and c to w. The priority union of Q and R, denoted Q .P. R, maps a to x, b to y, and c to w. That is, it includes all the pairs from Q and every pair from R that has as its upper element a string that does not occur as the upper string of any pair in Q. If some string occurs as the upper element of some pair in both Q and R, the priority union of Q and R only includes the pair in Q. Consequently Q .P. R in Figure 10 maps b to y instead of z.

The priority union operator .P. can be defined in terms of other regular expression operators in the Xerox calculus. A straightforward definition is given in Figure 11.

 

Figure 11:   Definition of priority union

        Q .P. R = Q | [~[Q.u] .o. R]        

The .u operator in Figure 11 extracts the ``upper'' language from a regular relation. Thus the expression ~[Q.u] denotes the set of strings that do not occur on the upper side of the Q relation. The effect of the composition in Figure 11 is to restrict R to mappings that concern strings that are not mapped to anything in Q. Only this subset of R is unioned with Q.

We define the desired operation, lenient composition, denoted .O., as a combination of ordinary composition and priority union (Figure 12).

 

Figure 12:   Definition of lenient composition

      R .O. C = [R .o. C] .P. R      

To better visualize the effect of the operation defined in Figure 12 one may think of the relation R as a set of mappings induced by GEN and the relation C as one of the constraints defined in Figure 8. The left side of the priority union, [R .o. C] restricts R to mappings that satisfy the constraint. That is, any pair whose lower side string is not in C will be eliminated. If some string in the upper language of R has no counterpart on the lower side that meets the constraint, then it is not present in [R .o. C].u but, for that very reason, it will be ``rescued'' by the priority union. In other words, if an underlying form has some output that can meet the given constraint, lenient composition enforces the constraint. If an underlying form has no output candidates that meet the constraint, then the underlying form and all its outputs are retained. The definition of lenient composition entails that the upper language of R is preserved in R .O. C.

Many people, including Hammond [8] and Frank and Satta [7], have independently had a similar idea without conceiving it as a finite-state operation. If one already knows about priority union, lenient composition is an obvious idea.

Let us illustrate the effect of lenient composition starting with the example in Figure 7 The composition of the input a with GEN yields a relation that maps a to the 14 outputs in Figure 7. We will leniently compose this relation with each of the constraints in the order of their ranking, starting with the HaveOns constraint (Figure 13). The lower-case operator .o. stands for ordinary composition, the upper case .O. for lenient composition.

 

Figure 13:   Cascade of constraint applications.

As Figure 13 illustrates, applying HaveOns by lenient composition removes most of the 14 output candidates produced by GEN. The resulting relation maps a to two outputs O[ ]N[a] and O[ ]N[a]D[ ]. The next highest-ranking constraint, NoCoda, removes the latter alternative. The twelve candidates that were eliminated by the first lenient composition are no longer under consideration.

The next two constraints in the sequence, FillNuc and Parse, obviously do not change the relation because the one remaining output candidate, O[ ]N[a], satisfies them. Up to this point, the distinction between lenient and ordinary composition does not make any difference because we have not exhausted the set of output candidates. However, when we bring in the last constraint, FillOns, the right half of the definition in Figure 12 has to come to the rescue; otherwise there would be no output for a.

This example demonstrates that the application of optimality constraints can be thought of as a cascade of lenient compositions that carry down an ever decreasing number of output candidates without allowing the set to become empty. Instead of intermediate representations (c.f. Figure 1) there are intermediate candidate populations corresponding to the columns in the left-to-right ordering of the constraint tableau.

Instead of applying the constraints one by one to the output provided by GEN for a particular input, we may also leniently compose the GEN relation itself with the constraints. Thus the suggestion made in Figure 9 is (nearly) correct after all, provided that we replace ordinary composition with lenient composition (Figure 14).

 

Figure 14:   Lenient cascade

                

                

The composite single transducer shown in Figure 14 maps a and any other input directly into its viable outputs without ever producing any failing candidates.