Next: Conclusion Up: Approximation and Exactness in Previous: Locality.

# Comparison

In this section we compare the two alternative approaches with respect to accuracy and the number of states of the resulting transducers. We distinguish between exact and approximating implementations. An implementation is exact if it produces the right result for all possible inputs.

Assume we have a transducer T which correctly implements an OT analysis, except that it perhaps fails to distinguish between different numbers of constraint violations for one or more relevant constraints. We can decide whether this T is exact as follows. T is exact if and only if T is exact with respect to each of the relevant constraints, i.e., for each constraint, T distinguishes between different numbers of constraint violations. In order to check whether T is exact in this sense for constraint C we create the transducer is_exact(T,C):


macro(is_exact(T,C),
T
o
mark_violation(C)
o
{(? - @) x [], @}*).

If there are inputs for which this transducer produces multiple outputs, then we know that T is not exact for C; otherwise T is exact for C. This reduces to the question of whether is_exact(T,C) is ambiguous. The question of whether a given transducer is ambiguous is shown to be decidable in [1]; and an efficient algorithm is proposed in [20].12Therefore, in order to check a given transducer T for exactness, it must be the case that for each of the constraints C, is_exact(T,C) is nonambiguous.

If a transducer T is not exact, we characterize the quality of the approximation by considering the maximum length of input strings for which T is exact. For example, even though T fails the exactness check, it might be the case that


[? ^,? ^,? ^,? ^,? ^]
o
T

in fact is exact, indicating that T produces the correct result for all inputs of length .

Suppose we are given the sequence of constraints:


have_ons >> fill_ons >> parse
>> fill_nuc >> no_coda

and suppose furthermore that we require that the implementation, using the counting approach, must be exact for all strings of length . How can we determine the level of precision for each of the constraints? A simple algorithm (which does not necessarily produce the smallest transducer) proceeds as follows. Firstly, we determine the precision of the first, most important, constraint by checking exactness for the transducer

gen oo P :: have_ons

for increasing values for P. As soon as we find the minimal P for which the exactness check succeeds (in this case for P=0), we continue by determining the precision required for the next constraint by finding the minimal value of P in:

gen oo 0 :: have_ons oo P :: fill_ons

We continue in this way until we have determined precision values for each of the constraints. In this case we obtain a transducer with 8269 states implementing:

gen oo 0 :: have_ons
oo 1 :: fill_ons
oo 8 :: parse
oo 5 :: fill_nuc
oo 4 :: no_coda

In contrast, using matching an exact implementation is obtained using a precision of 1 for the fill_nuc constraint; all other constraints have a precision of 0. This transducer contains only 28 states.

The assumption in OT is that each of the constraints is universal, whereas the constraint order differs from language to language. Prince and Smolensky identify nine interestingly different constraint orderings. These nine languages'' are presented in table 2.

Table 2: Nine different constraint orderings for syllabification, as given in Prince and Smolensky, chapter 6.
 id constraint order 1 have_ons fill_ons no_coda fill_nuc parse 2 have_ons no_coda fill_nuc parse fill_ons 3 no_coda fill_nuc parse fill_ons have_ons 4 have_ons fill_ons no_coda parse fill_nuc 5 have_ons no_coda parse fill_nuc fill_ons 6 no_coda parse fill_nuc fill_ons have_ons 7 have_ons fill_ons parse fill_nuc no_coda 8 have_ons parse fill_ons fill_nuc no_coda 9 parse fill_ons have_ons fill_nuc no_coda

In table 3 we compare the size of the resulting automata for the matching approach, as well as for the counting approach, for three different variants which are created in order to guarantee exactness for strings of length , and respectively.

Table 3: Comparison of the matching approach and the counting approach for various levels of exactness. The numbers indicate the number of states of the resulting transducer.
 Method Exactness Constraint order 1 2 3 4 5 6 7 8 9 matching exact 29 22 20 17 10 8 28 23 20 counting 95 220 422 167 10 240 1169 2900 4567 counting 280 470 1667 342 10 420 8269 13247 16777 counting 465 720 3812 517 10 600 22634 43820 50502

Finally, the construction of the transducer using the matching approach is typically much faster as well. In table 4 some comparisons are summarized.

Table 4: Comparison of the matching approach and the counting approach for various levels of exactness. The numbers indicate the CPU-time in seconds required to construct the transducer.
 Method Exactness Constraint order 1 2 3 4 5 6 7 8 9 matching exact 1.0 0.9 0.9 0.9 0.8 0.7 1.5 1.3 1.1 counting 0.9 1.7 4.8 1.6 0.5 1.9 10.6 18.0 30.8 counting 2.8 4.7 28.6 4.0 0.5 4.2 83.2 112.7 160.7 counting 6.8 10.1 99.9 8.6 0.5 8.2 336.1 569.1 757.2

Next: Conclusion Up: Approximation and Exactness in Previous: Locality.

2000-06-29