<OT> New Posting: ROA-978

[roa at ruccs.rutgers.edu]

ROA 978-0608

Violation Semirings in Optimality Theory

Jason Riggle <jriggle at uchicago.edu>

Direct link: http://roa.rutgers.edu/view.php3?roa=978


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.

Comments: 
Keywords: complexity, algorithms
Areas: Phonology,Computation,Formal Analysis
Type: Manuscript

Direct link: http://roa.rutgers.edu/view.php3?roa=978