1996/06/17 by Bruce Tesar, Tesar, Bruce
Computer Science · #Algorithms and Data Compression #Natural Language Processing Techniques #cmp-lg #cs.CL #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.cmp-lg/9606020
7 pages, uses aclap.sty. To appear in ACL 1996
arxiv created 1996/06/17 · arxiv updated 2009/11/30
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.