| ROA: | 206 |
|---|---|
| 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) |
| Length: | 8 |
| Abstract: | Efficient Generation in Primitive Optimality Theory Jason Eisner - University of Pennsylvania jeisner@linc.cis.upenn.edu 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 properties. 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 size. 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 OTFS. |
| Type: | Paper/tech report |
| Area/Keywords: | |
| Article: | Version 1 |