Some Computational Complexity Results for Synchronous Context-Free Grammars

Proceedings of Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing (HLT/EMNLP), pages 803–810, Vancouver, October 2005. c⃝2005 Association for Computational Linguistics Some Computational Complexity Results for Synchronous Context-Free Grammars Giorgio Satta Dept. of Information Engineering University of Padua via Gradenigo, 6/A I-35131 Padova Italy satta@dei.unipd.it Enoch Peserico Dept. of Information Engineering University of Padua via Gradenigo, 6/A I-35131 Padova Italy enoch@dei.unipd.it Abstract 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- free grammars working in a ‘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. 1 Introduction State of the art architectures for machine transla- tion are all based on mathematical models called translation models. Generally speaking, a transla- tion model accounts for all the elementary opera- tions that rule the process of translation between the words and the different word orderings of the source and target languages. Translation models are usu- ally enriched with statistical parameters, to drive the search toward the most likely translation(s). Special- ized algorithms are provided for the automatic esti- mation of these parameters from corpora of trans- lation pairs. Besides the task of natural language translation, statistical translation models are also ex- ploited in other applications, such as word align- ment, multilingual document retrieval and automatic dictionary construction. The most successful translation models that are found in the literature exploit finite-state machinery. The approach started with the so-called IBM mod- els (Brown et al., 1988), implementing a set of ele- mentary operations, such as movement, duplication and translation, that independently act on individ- ual words in the source sentence. These word-to- word models have been later enriched with the in- troduction of larger units such as phrases; see for instance (Och et al., 1999; Och and Ney, 2002). Still, the generative capacity of these models lies within the realm of finite-state machinery (Kumar and Byrne, 2003), so they are unable to handle nested structures and do not provide the expressivity required to process language pairs with very differ- ent word orderings. Recently, more sophisticated translation models have been proposed, borrowing from the theory of compilers and making use of synchronous rewrit- ing. In synchronous rewriting, two formal gram- mars are exploited, one describing the source lan- guage and the other describing the target language. Furthermore, the productions of the two gram- mars are paired and, in the rewriting process, such pairs are always applied synchronously. Formalisms based on synchronous rewriting have been empow- ered with the use of statistical parameters, and spe- cialized estimation and translation (decoding) algo- rithms were newly developed. Among the several proposals, we mention here the models presented in (Wu, 1997; Wu and Wong, 1998), (Alshawi et al., 2000), (Yamada and Knight, 2001), (Gildea, 2003) and (Melamed, 2003). …

Content truncated to 500 words