|Title:||Efficient Generation in Primitive Optimality Theory|
|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
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