[Author Login]
Title:Efficient Generation in Primitive Optimality Theory
Authors:Jason Eisner
Comment:8 pp. To appear in proceedings of ACL 1997 [Association for Computational Linguistics]. (19 April 1997)
Abstract: Efficient Generation in Primitive Optimality Theory

Jason Eisner - University of Pennsylvania


April 19, 1997

Proceedings of the 35th Annual Meeting of the Association for

Computational Linguistics and the 8th Conference of the European

Association for Computational Linguistics, Madrid, July 1997.

This paper introduces computational linguists to primitive

Optimality Theory (OTP), a clean and linguistically motivated

formalization of OT. OTP specifies the class of autosegmental

representations, the universal generator Gen, and the two simple

families of permissible constraints. It is therefore possible to

study its computational generation, comprehension, and learning


Some results are presented for the generation problem, that is,

for determining the optimal output:

1. OTP grammars can derive optimal surface forms with finite-state

methods adapted from Ellison (1994). These methods work even

if Gen produces infinitely many candidates, as is true under OTP.

2. Less restrictive theories using Generalized Alignment are

disturbingly powerful, and cannot avail themselves of these

finite-state methods.

3. Ellison's method takes time exponential on the size of the grammar.

4. Indeed, the OTP generation problem is shown NP-complete in this

sense. Thus, given a new grammar (e.g., when considering many

grammars during learning), generation will necessarily be very

slow in the worst case.

5. However, techniques are discussed for making Ellison's

approach fast and practical in the typical case. One simple trick

alone provides a 100-fold speedup on a grammar fragment of moderate


6. A more intricate technique has also been implemented and verified.

This technique uses a new finite-state notion, ``factored

automata,'' in which regular languages are represented compactly

via formal intersections of FSAs.

NOTE: After publication of this paper, the author also proved that OTP

has the same formal generative power as a finite-state formalism

("OTFS") in which Gen is a finite-state transducer (Frank & Satta,

1996) and each constraint is a weighted deterministic finite-state

automaton (following Ellison, 1994). However, OTP insists on

finer-grained rerankable constraints and encourages the use of

universal autosegmental tiers, so it has more explanatory force than

Type:Paper/tech report
Article:Version 1