Abstract
In Optimality Theory, grammaticality is defined in terms of optimization over a large (often infinite) space of candidates. This raises the question of how grammatical forms might be computed. This paper presents an analysis of the Basic CV Syllable Theory (Prince & Smolensky 1993) showing that, despite the nature of the formal definition, computing the optimal form does not require explicitly generating and evaluating all possible candidates. A specific algorithm is detailed which computes the optimal form in time that is linear in the length of the input. This algorithm will work for any grammar in Optimality Theory employing regular position structures and universal constraints which may be evaluated on the basis of local information.