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.

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:^{3}

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.

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
, 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.