Paper: Computing Optimal Descriptions For Optimality Theory Grammars With Context-Free Position Structures

ACL ID P96-1014
Title Computing Optimal Descriptions For Optimality Theory Grammars With Context-Free Position Structures
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 1996
Authors

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 pro- gramming approach (Tesar, 1994) (Tesar, 1995@ to computing optimal structural descriptions from regular to context-free structures. The generalization to context- free structures creates several complica- tions, all of which are overcome without compromising the core dynamic program- ming approach. The resulting algorithm has a time complexity cubic in the length of the input, and is applicable to gram- mars with universal constraints that ex- hibit context-free locality. 1 Computing Optimal Descriptions in Optimality Theory In Optimality Theory (Prince and Smolensky, 1993), grammaticality is define...