Lenient Composition.

In a recent paper, Karttunen [16] has provided a new formalization of Optimality Theory in terms of regular expressions. Optimality theory [20] is a framework for the description of phonological regularities which abandons rewrite rules. Instead, a universal function called GEN is proposed which maps input strings non-deterministically to many different output strings. In addition, a set of ranked universal constraints rule out many of the phonological representations generated by GEN. Some constraints can be conflicting. Therefore it might be impossible for a candidate string to satisfy all constraints. A string is allowed to violate a constraint as long as there is no other string which does not violate that constraint.

Procedurally, this mechanism can be understood as follows. Firstly, an input is mapped to a set of candidate output strings. This set of strings is then passed on to the most important constraint. This constraint removes many of the candidate strings. The remaining strings are passed on to the next important constraint, and so on. If the application of the constraint would remove all remaining candidate strings, then no strings are removed (constraints are violable). In the simplest case, only a single string survives all of the constraints. If none of the strings satisfy a given constraint, then the strings survive with the least number of violations of that constraint.

Karttunen formalizes GEN as a regular relation. Each of the constraints is itself a regular language allowing only the strings which satisfy the constraint (unless no strings satisfy the constraint). If the constraints were to be combined using ordinary composition, then the set of outputs would often be empty. Therefore, instead of composition Karttunen introduces an operation of lenient_composition which is closely related to a notion of defaults.

Informally, 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. Thus, it enforces the constraint C to those strings in S which have an output that satisfies the constraint:

$$\begin{minipage}[t]{.9\textwidth}\begin{verbatim}macro(prio... ...ion(S,C), priority_union(S o C,S)).\end{verbatim}\end{minipage}$$ (18)

Here, priority_union of two transductions Q and R is defined as the union of Q and the composition of the complement of the domain of Q with R; i.e. we obtain all pairs from Q, and moreover for all elements not in the domain of Q we apply R. Lenient composition of S and C is defined as the priority union of the composition of S and C (on the one hand) and S (on the other hand); i.e. we obtain the composition of S and C and moreover for all inputs for which that composition is empty we retain S.

Consider the example

$$\begin{minipage}[t]{.9\textwidth}\begin{verbatim}lenient_co... ...on({b x [b,b],a x [b,b]*},[b,b,b]*)\end{verbatim}\end{minipage}$$ (19)

The input transducer maps an a to an even number of b's, and it maps a b to two b's. If this transducer is leniently composed with the requirement that the result must be a string of b's divisible by 3, then the resulting transducer maps b to two b's, as before (since the constraint cannot be satisfied for any map of the input b), and it maps an a to a string of b's which is divisible by 6.

Karttunen illustrates the method by providing a formalization of the syllabification analysis in Optimality Theory. This formalization has been implemented in FSA5 and is given in the appendix.