[Author Login]
Title:Features in Optimality Theory: A Computational Model
Authors:Andrea Heiberg
Comment:Includes Java code. See http://www.u.arizona.edu/ic/heiberg for demo.
Abstract:Andrea Heiberg
University of Arizona

This dissertation presents a computational model of Optimality Theory
(OT) (Prince and Smolensky 1993). The model provides an efficient
solution to the problem of candidate generation and evaluation, and is
demonstrated for the realm of phonological features. Explicit
object-oriented implementations are proposed for autosegmental
representations (Goldsmith 1976 and many others) and violable OT
constraints and Gen operations on autosegmental representations.

Previous computational models of OT (Ellison 1995, Tesar 1995, Eisner
1997, Hammond 1997, Karttunen 1998) have not dealt in depth with
autosegmental representations. The proposed model provides a full
treatment of autosegmental representations and constraints on
autosegmental representations (Akinlabi 1996, Archangeli and
Pulleyblank 1994, Itô, Mester, and Padgett 1995, Kirchner 1993,
Padgett 1995, Pulleyblank 1993, 1996, 1998).

Implementing Gen, the candidate generation component of OT, is a
seemingly intractable problem. Gen in principle performs unlimited
insertion; therefore, it may produce an infinite candidate set. For
autosegmental representations, however, it is not necessary to think
of Gen as infinite. The Obligatory Contour Principle (Leben 1973,
McCarthy 1979, 1986) restricts the number of tokens of any one
feature type in a single representation; hence, Gen for autosegmental
features is finite.

However, a finite Gen may produce a candidate set of exponential size.
Consider an input representation with four anchors for each of five
features: there are (2^4 + 1)^5, more than one million, candidates
for such an input.

The proposed model implements a method for significantly reducing the
exponential size of the candidate set. Instead of first creating all
candidates (Gen) and then evaluating them against the constraint
hierarchy (Eval), candidate creation and evaluation are interleaved
(cf. Eisner 1997, Hammond 1997) in a Gen-Eval loop. At each pass
through the Gen-Eval loop, Gen operations apply to create the minimal
number of candidates needed for constraint evaluation; this candidate
set is evaluated and culled, and the set of Gen operations is reduced.
The loop continues until the hierarchy is exhausted; the remaining
candidate(s) are optimal.

In providing explicit implementations of autosegmental representations,
constraints, and Gen operations, the model provides a coherent view of
autosegmental theory, Optimality Theory, and the interaction between
the two.
Article:Version 1