Finite State Optimality Theory

The generate-and-test paradigm initially appears to be appropriate for optimality theory. If, as claimed in [2], Gen is a regular relation and if each constraint can be implemented as an identity transducer, then optimality theory analyses could be implemented as in fig. 1.

Figure 1: Optimality Theory as Generate and Test

The problem with this simple approach is that in OT, a constraint is allowed to be violated if none of the candidates satisfy that constraint. [12] treats this problem by providing a new operator for lenient composition, which is defined in terms of the auxiliary operation of priority union. In the FSA Utilities calculus, these operations can be defined as:³

macro(priority_union(Q,R), 
      {Q, ~domain(Q) o R}).
macro(lenient_composition(S,C), 
      priority_union(S o C, S)).

The effect here is that the lenient composition of S and C is the composition of S and C, except for those elements in the domain of S that are not mapped to anything by S o C. For these elements not in the domain of S o C, the effect is the same as the effect of S alone. We use the notation S lc C as a succinct notation for the lenient composition of S and C. Using lenient composition an OT analysis can be written as in fig. 2.

Figure 2: Optimality Theory as Generate and Test with Lenient Composition

The use of lenient composition, however, is not sufficient for implementing optimality theory. In general, a candidate string can violate a constraint multiple times and candidates that violate the constraint the least number of times need to be preferred. Lenient composition is sufficient to prefer a candidate that violates the constraint 0 times over a candidate that violates the constraint at least once. However, lenient composition cannot distinguish two candidates if the first contains one violation, and the second contains at least two violations.

The problem of implementing optimality theory becomes considerably harder when constraint violations need to be counted. As [3] have shown, an OT describes a regular relation under the assumptions that Gen is a regular relation, and each of the constraints is a regular relation which maps a candidate string to a natural number (indicating the number of constraint violations in that candidate), where the range of each constraint is finite. If constraints are defined in such a way that there is no bound to the number of constraint violations that can occur in a given string, then the resulting OT may describe a relation that is not regular. A simple example of such an OT (attributed to Markus Hiller) is the OT in which the inputs of interest are of the form [a*,b*], Gen is defined as a transducer which maps all a's to b's and all b's to a's, or alternatively, it performs the identity map on each a and b:

   {[(a x b)*,(b x a)*],     
    [(a x a)*,(b x b)*]}

This OT contains only a single constraint, *A: a string should not contain a. As can easily be verified, this OT defines the relation $\{(a^nb^m,a^nb^m) \vert n\leq m\} \cup \{(a^nb^m,b^na^m) \vert m\leq n\}$, which can easily be shown to be non-regular.

Although the OT described above is highly unrealistic for natural language, one might nevertheless expect that a constraint on syllable structure in the analysis of Prince & Smolensky would require an unbounded amount of counting (since words are of unbounded length), and that therefore such analyses would not be describable as regular relations. An important conclusion of this paper is that, contrary to this potential expectation, such cases in fact can be shown to be regular.