Finite state methods have proven quite successful for encoding rule-based generative phonology [6,8]. Recently, however, Optimality Theory [19] has emphasized phonological accounts with default constraints on surface forms. While Optimality Theory (OT) has been successful in explaining certain phonological phenomena such as conspiracies [15], it has been less successful for computation. The negative result of [3] has shown that in the general case the method of counting constraint violations takes OT beyond the power of regular relations. To handle such constraints, [12] has proposed a finite-state approximation that counts constraint violations up to a predetermined bound. Unlike previous approaches [2,25], Karttunen's approach is encoded entirely in the finite state calculus, with no extra-logical procedures for counting constraint violations.
In this paper, we will present a new approach that seeks to minimize constraint violations without counting. Rather than counting, our approach employs a filter based on matching constraint violations against violations in alternatively derivable strings. As in Karttunen's counting approach, our approach uses purely finite state methods without extra-logical procedures. We show that our matching approach is superior to the counting approach for both size of resulting automata and closeness of approximation. The matching approach can in fact exactly model many OT analyses where the counting approach yields only an approximation; yet, the size of the resulting automaton is typically much smaller.
In this paper we will illustrate the matching approach and compare it with the counting approach on the basis of the Prince & Smolensky syllable structure example [19,2,21], for each of the different constraint orderings identified in Prince & Smolensky.