A Note on the Complexity of Optimality Theory
Stephan Kepser, Uwe Mönnich · 2007
Optimality theory (OT), introduced by Prince and Smolensky (1993), is a linguistic framework in which the mapping of one level of linguistic representation to another is based on rules and filters. The rules generate candidate expressions in the target representation, which are subsequently checked against the filters, so that only those candidates remain that survive this filtering process. Germain to OT is the fact that filters or constraints are violable and ranked. Thus a candidate expression may violate a constraint, as long as alternative candidates violate more constraints or higher ranked constraints. An expression is optimal, if it violates the least number of lowest ranked constraints. Frank and Satta (1998) and Wartena (2000) have shown that these principles of OT can be fruitfully modeled using techniques from formal language theory. Both model the generator relation as a rational relation over regular languages and the constraints as regular languages; in (Frank and Satta, 1998) these are string languages, and in (Wartena, 2000) they are tree languages. We show here that generators can be extended to linear frontier-to-root tree transducers on linear context-free tree languages – with constraints being regular tree languages – while the computation of optimal candidates can still be performed using finite state techniques (over trees).