Introduction

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.