tailieunhanh - Báo cáo khoa học: "Computing Optimal Descriptions for Optimality Theory Grammars with Context-Free Position Structures"

This paper describes an algorithm for computing optimal structural descriptions for Optimality Theory grammars with context-free position structures. This algorithm extends Tesar's dynamic programming approach (Tesar, 1994) (Tesar, 1995@ to computing optimal structural descriptions from regular to context-free structures. The generalization to contextfree structures creates several complications, all of which are overcome without compromising the core dynamic programming approach. The resulting algorithm has a time complexity cubic in the length of the input, and is applicable to grammars with universal constraints that exhibit context-free locality. . | Computing Optimal Descriptions for Optimality Theory Grammars with Context-Free Position Structures Bruce Tesar The Rutgers Center for Cognitive Science The Linguistics Department Rutgers University Piscataway NJ 08855 USA Abstract This paper describes an algorithm for computing optimal structural descriptions for Optimality Theory grammars with context-free position structures. This algorithm extends Tesar s dynamic programming approach Tesar 1994 Tesar 1995a to computing optimal structural descriptions from regular to context-free structures. The generalization to context-free structures creates several complications all of which are overcome without compromising the core dynamic programming approach. The resulting algorithm has a time complexity cubic in the length of the input and is applicable to grammars with universal constraints that exhibit context-free locality. 1 Computing Optimal Descriptions in Optimality Theory In Optimality Theory Prince and Smolensky 1993 grammaticality is defined in terms of optimization. For any given linguistic input the grammatical structural description of that input is the description selected from a set of candidate descriptions for that input that best satisfies a ranked set of universal constraints. The universal constraints often conflict satisfying one constraint may only be possible at the expense of violating another one. These conflicts are resolved by ranking the universal constraints in a strict dominance hierarchy one violation of a given constraint is strictly worse than any number of violations of a lower-ranked constraint. When comparing two descriptions the one which better satisfies the ranked constraints has higher Harmony. Cross-linguistic variation is accounted for by differences in the ranking of the same constraints. The term linguistic input should here be understood as something like an underlying form. In phonology an input might be a string of segmental material in syntax it .