Violation Semirings in Optimality Theory
| Autor: | Jason Riggle |
|---|---|
| Rok vydání: | 2009 |
| Předmět: |
Discrete mathematics
Linguistics and Language Optimization problem Optimality theory Semiring Combinatorics TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES Factorization Rule-based machine translation Computer Science (miscellaneous) Algebraic number Commutative property Mathematics Merge (linguistics) |
| Zdroj: | Research on Language and Computation. 7:1-12 |
| ISSN: | 1572-8706 1570-7075 |
| Popis: | 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 γ 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 γ. This perspective thus makes it straightforward to evaluate the complexity of optimization for different constraint sets. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink