11.3.1 Finite-State Transducer Models of Optimality Theory

Now that we’ve sketched the linguistic motivations for Optimality Theory, let’s turn to the computational implications. We’ll explore two: implementation of OT via finite-state models, and stochastic versions of OT.

Can a derivation in Optimality Theory be implemented by finite-state transducers? Frank and Satta (1998), following the foundational work of Ellison (1994), showed that (1) if GEN is a regular relation (for example assuming the input doesn't contain context-free trees of some sort), and (2) if the number of allowed violations of any constraint has some finite bound, then an OT derivation can be computed by finite-state means. This second constraint is relevant because of a property of OT that we haven't mentioned: if two candidates violate exactly the same number of constraints, the winning candidate is the one which has the smallest number of violations of the relevant constraint.

One way to implement OT as a finite-state system was worked out by Karttunen (1998), following the above-mentioned work and that of Hammond (1997). In Karttunen's model, GEN is implemented as a finite-state transducer which is given an underlying form and produces a set of candidate forms. For example for the syllabification example above, GEN would generate all strings that are variants of the input with consonant deletions or vowel insertions, and their syllabifications.

Each constraint is implemented as a filter transducer that lets pass only strings which meet the constraint. For legal strings, the transducer thus acts as the identity mapping. For example, *COMPLEX would be implemented via a transducer that mapped any input string to itself, unless the input string had two consonants in the onset or coda, in which case it would be mapped to null.

The constraints can then be placed in a cascade, in which higher-ranked constraints are simply run first, as suggested in Fig. 11.9.

There is one crucial flaw with the cascade model in Fig. 11.9. Recall that the constraints-transducers filter out any candidate which violates a constraint. But in many derivations, including the proper derivation of ?i.lik.hin, even the optimal form still violates a constraint. The cascade in Fig. 11.8 would incorrectly filter it out, leaving

no surface form at all! Frank and Satta (1998) and Hammond (1997) both point out that it is essential to only enforce a constraint if it does not reduce the candidate set to zero. Karttunen (1998) formalizes this intuition with the lenient composition operator. Lenient composition is a combination of regular composition and an operation called priority union. The basic idea is that if any candidates meet the constraint these candidates will be passed through the filter as usual. If no output meets the constraint, lenient composition retains all of the candidates. Fig. 11.10 shows the general idea; the interested reader should see Karttunen (1998) for the details.