Permutation

In the general case, however, constraint violations need not line up. For example, if the order of constraints is somewhat rearranged as in:

parse oo fill_ons oo have_ons 
    oo fill_nuc oo no_coda

the matching approach is not exact: it will produce wrong results for an input such as `arts':

N[a]D[r]O[t]N[]D[s]      %cf: art@s
N[a]O[r]N[]D[t]O[s]N[]   %cf: ar@ts@

Here, the second output should not be produced because it contains one more violation of the fill_nuc constraint. In such cases, a limited amount of permutation can be used in the filter to make the marker symbols line up. The add_violation filter of fig. 4 can be extended with the following transducer which permutes marker symbols:

macro(permute_marker,
 [{[? *,(@ x []),? *,([] x @)],
   [? *,([] x @),? *,(@ x [])]}*,? *]).

Greater degrees of permutation can be achieved by composing permute_marker several times. For example:⁸

macro(add_violation(3),
 {(bracket x []), (? - bracket)}*   
                o
      [[? *,([] x @)]+, ? *]      
                o
        permute_marker          
                o
        permute_marker
                o
        permute_marker
                o
 {([] x bracket), (? - bracket)}*  ).

So we can incorporate a notion of `precision' in the definition of the optimality operator for the matching approach as well, by defining:

macro(Cands oo Prec :: Constraint),
        Cands
          o
 mark_violation(Constraint)
          o
   ~ range(Cands
             o
       mark_violation(Constraint)
             o
        add_violation(Prec))
          o
   { (@ x []),(? - @)}*  ).

The use of permutation is most effective when constraint violations in alternative candidates tend to occur in corresponding positions. In the worst case, none of the violations may line up. Suppose that for some constraint, the input ``bebop'' is marked up as:

c1:   @ b @ e    b    o    p
c2:     b   e  @ b  @ o  @ p

In this case, the precision needs to be two in order for the markers in c1 to line up with markers in c2. Similarly, the counting approach also needs a precision of two in order to count the two markers in c1 and prefer this over the greater than two markers in c2. The general pattern is that any constraint that can be treated exactly with counting precision N, can also be handled by matching with precision less than or equal to N. In the other direction, however, there are constraints, such as those in the Prince and Smolensky syllabification problem, that can only be exactly implemented by the matching approach.

For each of the constraint orderings discussed by Prince and Smolensky, it turns out that at most a single step of permutation (i.e. a precision of 1) is required for an exact implementation. We conclude that this OT analysis of syllabification is regular. This improves upon the result of [12]. Moreover, the resulting transducers are typically much smaller too. In §5 we present a number of experiments which provide evidence for this observation.