Next: Priority Union for lexical
Up: Regular Expression Operators in
Previous: Regular Expression Operators in
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 nondeterministically 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:

(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

(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.
Next: Priority Union for lexical
Up: Regular Expression Operators in
Previous: Regular Expression Operators in
20000703