On the Complexity of Alignment Problems in Two Synchronous Grammar Formalisms

Anders SøgaardNAACL 2009 · OpenReview

Abstract: Anders Søgaard. Proceedings of the Third Workshop on Syntax and Structure in Statistical Translation (SSST-3) at NAACL HLT 2009.

2009.

Introduction

In syntax-based machine translation, synchronous grammars model the transformation of sentences between languages. A fundamental challenge is the alignment problem: determining the mapping between words in a source sentence and a target sentence given a specific grammar. This paper investigates the computational complexity of this problem across two formalisms: Inversion Transduction Grammars (ITGs) and (2,2)-Bounded Range Concatenation Grammars ((2,2)-BRCGs).

Synchronous Grammar Formalisms

The study focuses on two primary formalisms with differing levels of expressivity:

  1. Inversion Transduction Grammars (ITGs): Widely used but structurally limited, ITGs cannot represent certain complex alignments, such as discontinuous or "inside-out" mappings.
  2. Range Concatenation Grammars (specifically (2,2)-BRCGs): A more expressive class capable of inducing any possible word alignment.

Despite the difference in expressivity, both formalisms share a universal recognition complexity of $O(n^6)$. This paper explores why the added power of (2,2)-BRCGs does not immediately lead to higher complexity in general recognition, but rather manifests when common linguistic constraints are applied.

Methodology: Complexity Analysis

The author defines 15 variations of the alignment problem by applying three types of constraints:

  • 1:1 Alignments: Each source word maps to exactly one target word.
  • Island-free (IF): All words must be aligned (no "islands" of unaligned text).
  • Sure-possible sorted (SP): Distinguishing between certain and potential alignments.

To prove NP-hardness for (2,2)-BRCGs under these constraints, the paper employs polynomial-time reductions from known NP-complete problems. For instance, the 1:1 alignment restriction is proven intractable via a reduction from the Hamiltonian Circuit problem.

Graph construction used in the reduction from the Hamiltonian Circuit problem to restricted alignment.

Key Results: The NP-hard Wall

The central finding is a sharp divergence in complexity between the two formalisms when constraints are introduced. While ITGs remain solvable in $O(n^6)$ for all 15 variations, (2,2)-BRCGs become NP-complete in every single case. The author provides a definitive table (Figure 1) comparing these results.

Figure 1: Complexity of ITGs vs. (2,2)-BRCGs across 15 restricted alignment scenarios.

This "Expressivity Paradox" suggests that (2,2)-BRCGs maintain polynomial efficiency only by being "sloppy"—they avoid NP-hardness by failing to enforce global properties like ensuring every word is translated exactly once. Once these global constraints are imposed, the search space becomes intractable.

Conclusion and Future Work

The results highlight a significant trade-off in machine translation: choosing a grammar that can represent any alignment (like BRCG) necessitates facing NP-hard search problems when enforcing basic translation rules. Conversely, ITGs remain efficient by restricting the types of alignments they can represent. Future research may seek a middle ground—formalisms more expressive than ITGs that still allow for efficient constrained alignment.

Summary updated

Abstract

Anders Søgaard. Proceedings of the Third Workshop on Syntax and Structure in Statistical Translation (SSST-3) at NAACL HLT 2009. 2009.
BibTeX
@inproceedings{sgaard2009complexity,
  author = {Anders Søgaard},
  title = {{On the Complexity of Alignment Problems in Two Synchronous Grammar Formalisms}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2009},
  url = {https://openreview.net/forum?id=r3qJBNcZmp8},
}
Figure