[Author Login]
Title:Violation Semirings in Optimality Theory
Authors:Jason Riggle
Abstract:This paper provides a brief algebraic characterization of constraint violations in Optimality Theory (OT). I show that if violations are taken to be multisets over a fixed basis set CON then the merge operator on multisets and a `min' operation expressed in terms of harmonic inequality provide a semiring over violation profiles. This semiring allows standard optimization algorithms to be used for OT grammars with weighted finite-state constraints in which the weights are violation-multisets. Most usefully, because multisets are unordered, the merge operation is commutative and thus it is possible to give a single graph representation of the entire class of grammars (i.e. rankings) for a given constraint set. This allows a neat factorization of the optimization problem that isolates the main source of complexity into a single constant $gamma$ denoting the size of the graph representation of the whole constraint set. I show that the computational cost of optimization is linear in the length of the underlying form with the multiplicative constant $gamma$. This perspective thus makes it straightforward to evaluate the complexity of optimization for different constraint sets.
Type:Paper/tech report
Area/Keywords:Phonology,Computation,Formal Analysis
Article:Version 1