[Author Login]
[Home]
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