tailieunhanh - Báo cáo khoa học: "Efficient Generation in Primitive Optimality Theory"

This paper introduces primitive Optimality Theory (OTP), a linguistically motivated 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 using Generalized Alignment, OTP's optimal surface forms can be generated with finite-state methods adapted from (Ellison, 1994). Unfortunately these methods take time exponential on the size of the grammar. Indeed the generation problem is shown NP-complete in this sense. . | Efficient Generation in Primitive Optimality Theory Jason Eisner Dept of Computer and Information Science University of Pennsylvania 200 s. 33rd St. Philadelphia PA 19104-6389 USA j Abstract This paper introduces primitive Optimality Theory OTP a linguistically motivated 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 using Generalized Alignment OTP s optimal surface forms can be generated with finite-state methods adapted from Ellison 1994 . Unfortunately these methods take time exponential on the size of the grammar. Indeed the generation problem is shown NP-complete in this sense. However 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 improvements is a new finite-state notion factored automata where regular languages are represented compactly via formal intersections of FSAs. 1 Why formalize OT Phonology has recently undergone a paradigm shift. Since the seminal work of Prince Smolensky 1993 phonologists have published literally hundreds of analyses in the new constraint-based framework of Optimality Theory or OT. Old-style derivational analyses have all but vanished from the linguistics conferences. The price of this creative ferment has been a certain lack of rigor. The claim for as Universal Grammar is not substantive or falsifiable without formal definitions of the putative Universal Grammar objects Repns Con and Gen see below . Formalizing OT is necessary not only to flesh it out as a linguistic theory but also for the sake of computational phonology. Without knowing what classes of constraints may appear in grammars we can say only so much about the properties of the system or about algorithms for generation .