Computing Optimal Descriptions for Optimality Theory Grammars with Context-Free Position Structures
<|reference_start|>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 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.<|reference_end|>
@article{tesar1996computing,
    title={Computing Optimal Descriptions for Optimality Theory Grammars with
  Context-Free Position Structures},
    author={Bruce Tesar (Rutgers University)},
    journal={arXiv preprint arXiv:cmp-lg/9606020},
    year={1996},
    archivePrefix={arXiv},
    eprint={cmp-lg/9606020},
    primaryClass={cmp-lg cs.CL}
}