Synchronous Context-Free Grammars (SCFGs) are widely used for modeling the correspondence between two languages in statistical machine translation. Bottom-up, dynamic programming (DP) parsers for SCFGs can be designed by generalizing the CKY algorithm for standard CFGs: however, the space complexity of the parsing algorithm depends on the maximum "fan-out" of the DP chart items, that is, on the maximum number of non continuous substrings of right-hand side non-terminals which have been recognized covering some set of spans in the input string pair. In this talk, we study the problem of minimizing this maximum fan-out when considering parsing strategies for SCFG rules which add one non-terminal at a time. In particular, we first show that this problem is related to the minimum cutwidth problem restricted to a special class of graphs, called red-blue graphs. We then prove that this latter problem is NP-complete. Finally, we conclude with an interesting open problem related to the carving width of red-blue graphs, which arises when considering more general parsing strategies for SCFG rules.

This is a joint work with Daniel Gildea, Andrea Marino, Gianluca Rossi, and Giorgio Satta.