It has been recognized for some time that Optimality Theory (OT), introduced by Prince and Smolensky [24], is from a computational point of view closely related to classical phonological rewrite systems (Chomsky and Halle [1]) and to two-level descriptions (Koskenniemi [21]).
Ellison [6] observes that the GEN function of OT can be regarded as a regular relation and that OT constraints seem to be regular. Thus each constraint can be modeled as a transducer that maps a string to a sequence of marks indicating the presence or absence of a violation. The most optimal solution can then be found by sorting and comparing the marks. Frank and Satta [7] give a formal proof that OT models can be construed as regular relations provided that the number of violations is bounded. Eisner [3,4,5] develops a typology of OT constraints that corresponds to two types of rules in two-level descriptions: restrictions and prohibitions.
The practice of marking and counting constraint violations is closely related to the tableau method introduced in Prince and Smolensky for selecting the most optimal output candidate. Much of the current work in optimality theory consists of constructing tableaux that demonstrate the need for particular constraints and rankings that allow the favored candidate to emerge with the best score.
From a computational viewpoint, this evaluation method is suboptimal. Although the work of GEN and the assignment of violation marks can be carried out by finite-state transducers, the sorting and counting of the marks envisioned by Ellison and subsequent work (Walther [26]) is an off-line activity that is not a finite-state process. This kind of optimality computation cannot be straightforwardly integrated with other types of linguistic processing (morphological analysis, text-to-speech generation etc.) that are commonly performed by means of finite-state transduction.
This paper demonstrates that the computation of the most optimal surface realizations of any input string can be carried out entirely within a finite-state calculus, subject to the limitation (Frank and Satta [7]) that the maximal number of violations that need to be considered is bounded. We will show that optimality constraints can be treated computationally in a similar manner to two-level constraints and rewrite rules. For example, optimality constraints can be merged with one another, respecting their ranking, just as it is possible to merge rewrite rules and two-level constraints. A system of optimality constraints can be imposed on a finite-state lexicon creating a transducer that maps each member of a possibly infinite set of lexical forms into its most optimal surface realization, and vice versa.
For the sake of conciseness, we limit the discussion to optimality theory as originally presented in Prince and Smolensky [24]. The techniques described below can also be applied to the correspondence version of the theory (McCarthy and Prince [22]) that expands the model to encompass output/output constraints between reduplicant and base forms.
To set the stage for discussing the application and merging of optimality constraints it is useful to look first at the corresponding operations in the context of rewrite rules and two-level constraints. Thus we can see both the similarities and the differences among the three approaches.