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].¹²Therefore, 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 $\leq 5$.

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 $\leq 10$. 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 $\gg$ fill_ons $\gg$ no_coda $\gg$ fill_nuc $\gg$ parse
2	have_ons $\gg$ no_coda $\gg$ fill_nuc $\gg$ parse $\gg$ fill_ons
3	no_coda $\gg$ fill_nuc $\gg$ parse $\gg$ fill_ons $\gg$ have_ons
4	have_ons $\gg$ fill_ons $\gg$ no_coda $\gg$ parse $\gg$ fill_nuc
5	have_ons $\gg$ no_coda $\gg$ parse $\gg$ fill_nuc $\gg$ fill_ons
6	no_coda $\gg$ parse $\gg$ fill_nuc $\gg$ fill_ons $\gg$ have_ons
7	have_ons $\gg$ fill_ons $\gg$ parse $\gg$ fill_nuc $\gg$ no_coda
8	have_ons $\gg$ parse $\gg$ fill_ons $\gg$ fill_nuc $\gg$ no_coda
9	parse $\gg$ fill_ons $\gg$ have_ons $\gg$ fill_nuc $\gg$ 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 $\leq 5$, $\leq 10$ and $\leq 15$ 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	$\leq 5$	95	220	422	167	10	240	1169	2900	4567
counting	$\leq 10$	280	470	1667	342	10	420	8269	13247	16777
counting	$\leq 15$	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	$\leq 5$	0.9	1.7	4.8	1.6	0.5	1.9	10.6	18.0	30.8
counting	$\leq 10$	2.8	4.7	28.6	4.0	0.5	4.2	83.2	112.7	160.7
counting	$\leq 15$	6.8	10.1	99.9	8.6	0.5	8.2	336.1	569.1	757.2