| ROA: | 363 |
|---|---|
| Title: | Optima |
| Authors: | Vieri Samek-Lodovici, Alan Prince |
| Comment: | |
| Length: | 58 |
| Abstract: | Optima Vieri Samek-Lodovici(University College, London) Alan Prince (Rutgers University) 11/22/99 Linguistic typology turns on the distinction between candidates that are optimal under some ranking and candidates that are never optimal under any ranking: this is the distinction between potential 'winners' and perpetual 'losers'. In this paper we develop necessary and sufficient conditions that decide the winner/loser status of any candidate without requiring that rankings be examined. To facilitate the discussion, we formulate Optimality Theory in a way that emphasizes its order-theoretic underpinnings. Generalizing the familiar notion of harmonic bounding (Samek-Lodovici 1992, Prince & Smolensky 1993), we show that a candidate is a loser if and only if it has a non-null bounding set that meets two general conditions. Checking these conditions requires no reference to ranking at all; it is done on a constraint-by-constraint basis, and the only information needed is the relation on each constraint between the putative loser and the members of a proposed bounding set for it. Bounding sets are limited in size: they need be no larger than the constraint set, and will typically be much smaller. A set of candidates that does not satisfy the bounding set criteria can nonetheless certify a loser's status by providing, for each ranking, a candidate that is better than the loser; but any such set must contain a bounding set. The notion of bounding set thus yields a complete, ranking-free characterization of loser status. How is a bounding set to be found? The pursuit of the bounding set leads, by recursive exclusion of nonbounds, to the construction of a 'favoring hierarchy' from the constraint set. The favoring hierarchy is, we show, equivalent to the 'target hierarchy' of Tesar 1995 and Tesar & Smolensky 1998, and its recursive definition parallels their Recursive Constraint Demotion (RCD) algorithm. A candidate is a winner if and only if it has a favoring hierarchy that exhausts the constraint set. An exhaustive favoring hierarchy leads to a ranking on which a candidate is guaranteed to win, if it wins on any ranking at all. For a loser, the construction of its favoring hierarchy leaves a residue of constraints that cannot be integrated into the hierarchy and a corresponding set of refractory candidates that cannot be eliminated in competition with the loser. From these residual candidates, a bounding set can be readily constructed; in addition, the maximal bounding set is identified. The size of the residual set of constraints also leads to a tighter upper bound on size of a loser's minimal bounding sets. These results provide the analyst with new tools for handling the crucial winner/loser distinction. They affirm the theoretical centrality of RCD and its associated construct, the favoring hierarchy, which originally arose in the context of learning and computational issues, but here proves to be indispensable for understanding the core structure of the theory. The fully order-theoretic approach developed here also provides a new perspective on the key notions of bounding, evaluation, and optimality. |
| Type: | Paper/tech report |
| Area/Keywords: | |
| Article: | Version 1 |