Some Computational Complexity Results for Synchronous Context-Free Grammars 
 
 This paper investigates some computational problems associated with probabilistic translation models that have recently been adopted in the literature on machine translation . These models can be viewed as pairs of probabilistic context-free grammars working in a 'synchronous' way. Two hardness results for the class NP are reported, along with an exponential time lower-bound for certain classes of algorithms that are currently used in the literature. 