Paper: Efficient Generation In Primitive Optimality Theory

ACL ID P97-1040
Title Efficient Generation In Primitive Optimality Theory
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 1997

This paper introduces primitive Optimal- ity Theory (OTP), a linguistically moti- vated formalization of OT. OTP specifies the class of autosegmental representations, the universal generator Gen, and the two simple families of permissible constraints. In contrast to less restricted theories us- ing Generalized Alignment, OTP's opti- mal surface forms can be generated with finite-state methods adapted from (Ellison, 1994). Unfortunately these methods take time exponential on the size of the gram- mar. Indeed the generation problem is shown NP-complete in this sense. How- ever, techniques are discussed for making Ellison's approach fast in the typical case, including a simple trick that alone provides a 100-fold speedup on a grammar fragment of moderate size. One avenue for future improvemen...