Paper: Some Computational Complexity Results For Synchronous Context-Free Grammars

ACL ID H05-1101
Title Some Computational Complexity Results For Synchronous Context-Free Grammars
Venue Conference on Empirical Methods in Natural Language Processing
Session Main Conference
Year 2005
Authors

This paper investigates some computa- tional problems associated with proba- bilistic translation models that have re- cently been adopted in the literature on machine translation. These models can be viewed as pairs of probabilistic context- freegrammarsworkingina‘synchronous’ way. Two hardness results for the class NP are reported, along with an exponen- tial time lower-bound for certain classes of algorithms that are currently used in the literature.