[Author Login]
Title:Generating Contenders
Authors:Jason Riggle
Abstract:In Optimality Theory, a contender is a candidate that is optimal under some ranking of the constraints. When the candidate generating function Gen and all of the constraints are rational (i.e., representable with (weighted) finite state automata) it is possible to generate the entire set of contenders for a given input form in much the same way that optima for a single ranking are generated. This paper gives a brief introduction to rational constraints and provides an algorithm for generating contenders whose complexity, modulo the number of contenders generated, is linear in the length of the underlying form with a multiplicative constant representing the size of the finite-state representation of the constraint set.
Type:Paper/tech report
Area/Keywords:Computation,Formal Analysis
Article:Version 1