OT Syntax – Decidability of Generation-based Optimization

OT Syntax: Decidability of Generation-based Optimization � Jonas Kuhn Department of Linguistics Stanford University jonask@stanford.edu Abstract In Optimality-Theoretic Syntax, optimiza- tion with unrestricted expressive power on the side of the OT constraints is unde- cidable. This paper provides a proof for the decidability of optimization based on constraints expressed with reference to lo- cal subtrees (which is in the spirit of OT theory). The proof builds on Kaplan and Wedekind’s (2000) construction showing that LFG generation produces context- free languages. 1 Introduction Optimality-Theoretic (OT) grammar systems are an interesting alternative to classical formal grammars, as they construe the task of learning from data in a meaning-based way: a form is defined as gram- matical if it is optimal (most harmonic) within a set of generation alternatives for an underlying logical form. The harmony of a candidate analysis depends on a language-specific ranking ( � ) of violable con- straints, thus the learning task amounts to adjusting the ranking over a given set of constraints. (1) Candidate �� is more harmonic than �� iff it incurs fewer violations of the highest-ranking constraint �� in which �� and �� differ. The comparison-based setup of OT learning is closely related to discriminative learning approaches in probabilistic parsing (Johnson et al., 1999; Rie- zler et al., 2000; Riezler et al., 2002),1 however the comparison of generation alternatives – rather than parsing alternatives – adds the possibility of system- atically learning the basic language-specific gram- matical principles (which in probabilistic parsing are typically fixed a priori, using either a treebank- derived or a manually written grammar for the given  This work was supported by a postdoctoral fellowship of the German Academic Exchange Service (DAAD). 1This is for instance pointed out by (Johnson, 1998). language). The “base grammar” assumed as given can be highly unrestricted in the OT setup. Using a linguistically motivated set of constraints, learning proceeds with a bias for unmarked linguistic struc- tures (cf. e.g., (Bresnan et al., 2001)). For computational OT syntax, an interleaving of candidate generation and constraint checking has been proposed (Kuhn, 2000). But the decidability of the optimization task in OT syntax, i.e., the iden- tification of the optimal candidate(s) in a potentially infinite candidate set, has not been proven yet.2 2 Undecidability for unrestricted OT Assume that the candidate set is characterized by a context-free grammar (cfg)  , plus one addi- tional candidate ‘yes’. There are two constraints (   �   ):   is violated if the candidate is neither ‘yes’ nor a structure generated by a cfg   ;   is vi- olated only by ‘yes’. Now, ‘yes’ is in the language defined by this system iff there are no structures in  that are also in   . But the emptiness problem for the intersection of two context-free languages is known to be undecidable, so the optimization task for unrestricted OT is undecidable too.3 However, it is not in the spirit of OT to have extremely powerful …

Content truncated to 500 words