2 Background: rewrite rules and two-level constraints

As is well-known, phonological rewrite rules and two-level constraints can be implemented as finite-state transducers (Johnson [9], Karttunen, Koskenniemi and Kaplan [14], Kaplan and Kay [10]).

The application of a system of rewrite rules to an input string can be modeled as a cascade of transductions, that is, a sequence of compositions that yields a relation mapping the input string to one or more surface realizations. The application of a set of two-level constraints is a combination of intersection and composition (Karttunen [18]).

To illustrate the idea of rule application as composition, let us take a concrete example, the well-known vowel alternations in Yokuts (Kisseberth [20], Cole and Kisseberth [2], McCarthy [23]). Yokuts vowels are subject to three types of alternations:

• Underspecified suffix vowels are rounded in the presence of a stem vowel of the same height: dub+hIn $\rightarrow$ dubhun, bok'+Al $\rightarrow$ bok'ol.
• Long high vowels are lowered: ?u:t+It $\rightarrow$ ?o:tut, mi:k+It $\rightarrow$ me:kit.
• Vowels are shortened in closed syllables: sa:p $\rightarrow$ sap, go:b+hIn $\rightarrow$ gobhin.

Because of examples such as ?u:t+hIn $\rightarrow$ ?othun, the rules must be applied in the given order. Rounding must precede lowering because the suffix vowel in ?u:t+hIn emerges as u. Shortening must follow lowering because the stem vowel in ?u:t+hIn would otherwise remain high giving ?uthun rather than ?othun as the final output.

These three rewrite rules can be formalized straightforwardly as regular replace expressions (Karttunen [19]) and compiled into finite-state transducers. The derivation ?u:t+hIn $\rightarrow$ ?othun can thus be modeled as a cascade of three compositions that yield a transducer that relates the input directly to the final output.

 

Figure 1:   Cascade of rewrite rule applications.

The first step, the composition of the initial network (an identity transducer on the string ?u:t+hIn) with the rounding transducer, produces the network that maps between ?u:t+hIn and ?u:t+hun. The symbol .o. in Figure 1 denotes the composition operation.

It is important to realize that the result of each rule application in Figure 1 is not an output string but a relation. The first application produces a mapping from ?u:t+hIn to ?u:t+hun. In essence, it is the original Rounding transducer restricted to the specific input. The resulting network represents a relation between two languages (= sets of strings). In this case both languages contain just one string; but if the Rounding rule were optional, the output language would contain two strings: one with, the other without rounding.

At the next step in Figure 1, the intermediate output created by the Rounding transducer is eliminated as a result of the composition with the Lowering transducer. The final stage is a transducer that maps directly between the input string and its surface realization without any intermediate stages.

We could achieve this same result in a different way: by first composing the three rules to produce a transducer that maps any underlying form directly to its Yokuts surface realization (Figure 2) and then applying the resulting single transducer to the particular input.

 

Figure 2:   Yokuts vowel alternations.

          

          

The small network (21 states) pictured in Figure 2 merges the three rules and thus represents the complexity of Yokuts vowel alternations without any ``serialism'', that is, without any intermediate representations.

In the context of the two-level model, the Yokuts vowel alternations can be described quite simply. The two-level version of the rounding rule controls rounding by the lexical context. It ignores the surface realization of the trigger, the underlyingly high stem vowel. The joint effect of the lowering and shortening constraints is that a lexical u: in ?u:t+hIn is realized as o. Thus a two-level description of the Yokuts alternations consists of three rule transducers operating in parallel (Figure 3).

 

Figure 3:   Parallel two-level constraints.

The application of a two-level system to an input can be formalized as intersecting composition (Karttunen [18]). It involves constructing a partial intersection of the constraint networks and composing it with the input. We can of course carry out the intersection of the rules independently of any particular input. This merging operation results in the very same 21-state transducer as the composition of the corresponding rewrite rules pictured in Figure 2.

Thus the two descriptions of Yokuts sketched above are completely equivalent in that they yield the same mapping between underlying and surface forms. They decompose the same complex vowel alternation relation in different ways into a set of simpler relations that are easily understood and manipulated. As we will see shortly, optimality theory can be characterized as yet another way of achieving this kind of decomposition.

The fundamental computational operation for rewrite rules is composition, as it is involved both in the application of rules to strings and in merging the rules themselves. For two-level rules, the corresponding operations are intersecting composition and intersection.

Turning now to optimality theory, our main interest will be in finding what the corresponding computations are in this new paradigm. What does applying a constraint mean in the context of optimality theory? Can optimality constraints be merged while taking into account their ranking?