---
title: "Binarization of Synchronous Context-Free — Huang 2009"
description: "Syntax-based machine translation built on synchronous context-free grammars (SCFGs) or tree transducers, such as rules extracted following Galley et al."
authors: ["Liang Huang", "Hao Zhang", "Daniel Gildea", "Kevin Knight"]
year: 2009
venue: "Computational Linguistics"
source: "https://aclanthology.org/J09-4009/"
doi: "10.1162/coli.2009.35.4.35406"
licence: "CC BY-NC-SA 3.0 (ACL Anthology, before 2016)"
licence_url: "https://creativecommons.org/licenses/by-nc-sa/3.0/"
summary_licence: "Elamur Cosmic License"
canonical: "https://research.elamur.ai/free/papers/huang-2009-binarization-synchronous-context-free-grammars/"
---
[Elamur Research](https://md.research.elamur.ai/) · [this page in HTML](https://research.elamur.ai/free/papers/huang-2009-binarization-synchronous-context-free-grammars/)

[home](https://md.research.elamur.ai/) / [papers](https://md.research.elamur.ai/free/papers/) / [2009](https://md.research.elamur.ai/free/papers/2009/) / Binarization of Synchronous Context-Free Grammars

# Binarization of Synchronous Context-Free Grammars

**Authors:** [Liang Huang](https://md.research.elamur.ai/free/authors/liang-huang/), [Hao Zhang](https://md.research.elamur.ai/free/authors/hao-zhang/), [Daniel Gildea](https://md.research.elamur.ai/free/authors/daniel-gildea/), [Kevin Knight](https://md.research.elamur.ai/free/authors/kevin-knight/) · **Year:** 2009 · **Venue:** Computational Linguistics · **Licence:** [CC BY-NC-SA 3.0 (ACL Anthology, before 2016)](https://creativecommons.org/licenses/by-nc-sa/3.0/)

**Links:** [Publisher's page](https://aclanthology.org/J09-4009/) · [PDF](https://aclanthology.org/J09-4009.pdf) · [DOI 10.1162/coli.2009.35.4.35406](https://doi.org/10.1162/coli.2009.35.4.35406) · [OpenAlex](https://openalex.org/W2099851297)

**Citations:** 56 citations (openalex-snapshot · 2026-10-14) · [28](#cited-by) in our library, of the 140673 papers whose bibliographies we read

## Summary
Syntax-based machine translation built on synchronous context-free grammars (SCFGs) or tree transducers, such as rules extracted following Galley et al. (2004), is expensive to decode. The cost grows exponentially with the number of nonterminals in a rule, because the two languages can reorder constituents freely. Unlike monolingual CFGs, synchronous rules cannot always be broken into binary pieces. The authors formalize synchronous binarization, which splits a rule so that every intermediate (virtual) nonterminal covers a contiguous span in both languages. This lets n-gram language model scores be applied early in decoding. They give a linear-time algorithm that binarizes any rule for which this is possible. On a large Chinese-to-English syntax-based system, almost all extracted rules were binarizable. The binarized grammar made decoding both faster and more accurate than a baseline that binarizes only the source side. For the rare non-binarizable rules, the paper proves results that shrink the space of parsing strategies. It also offers an exact search method and a polynomial-time approximation.

## Key points
- With monolingual (source-side-only) binarization, m-gram-integrated decoding costs O(|w|^(3+2n(m−1))), which grows with rule size n. Synchronous binarization reduces this to O(|w|^(3+4(m−1))), which does not depend on rule size.
- The binarization algorithm runs in linear time. The resulting rule set supports efficient synchronous parsing and decoding with an integrated n-gram LM.
- The end-to-end evaluation uses a large-scale Chinese-to-English syntax-based system. It compares synchronous binarization against monolingual binarization and against a state-of-the-art phrase-based system.
- The paper presents what it describes as the first real non-binarizable examples, each checked by native speakers.
- Finding the optimal strategy for arbitrary SCFG rules is believed to be NP-complete. The authors prove that strategies respecting decomposition boundaries are never worse. In one worked example, this reduces the complexity from O(|w|^(7m−3)) to O(|w|^(5m−2)).

*Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.*

Fields: [Machine translation](https://md.research.elamur.ai/free/shelves/machine-translation/) · [Natural language processing](https://md.research.elamur.ai/free/shelves/nlp/)

## Cited by

Cited by

28 papers of our library cite it (of the 140673 whose bibliographies we read); 1 of them have a page here, 27 not yet.

- [Why Synchronous Tree Substitution Grammars?](https://md.research.elamur.ai/free/papers/maletti-2010-why-synchronous-tree-substitution-grammars/)

## Cite

The paper itself, not this page. BibTeX from the library's record of the work.

```bibtex
@article{huang2009binarization,
  title = {{Binarization of Synchronous Context-Free Grammars}},
  author = {Huang, Liang and Zhang, Hao and Gildea, Daniel and Knight, Kevin},
  journal = {Computational Linguistics},
  year = {2009},
  doi = {10.1162/coli.2009.35.4.35406},
  url = {https://doi.org/10.1162/coli.2009.35.4.35406}
}
```

- [← previous Better Word Alignments with Supervised ITG Models](https://md.research.elamur.ai/free/papers/haghighi-2009-better-word-alignments-supervised-itg/)
- [next → CATiB: The Columbia Arabic Treebank](https://md.research.elamur.ai/free/papers/aclbulk-2009-habash-catib-columbia-arabic-treebank/)
- [↑ back to papers of 2009](https://md.research.elamur.ai/free/papers/2009/)

## References

33 references, 7 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

1. Aho, Albert V. and Jeffery D. Ullman. 1972. The Theory of Parsing, Translation, and Compiling, volume 1. Prentice-Hall, Englewood Cliffs, NJ. [find](https://scholar.google.com/scholar?q=Aho%2C+Albert+V%2E+and+Jeffery+D%2E+Ullman%2E+1972%2E+The+Theory+of+Parsing%2C+Translation%2C+and+Compiling%2C+volume+1%2E+Prentice%2DHall%2C+Englewood+Cliffs%2C+NJ%2E)
2. Arnborg, Stefen, Derek G. Corneil, and Andrzej Proskurowski. 1987. Complexity of finding embeddings in a k-tree. SIAM Journal of Algebraic and Discrete Methods, 8:277–284. [↗](https://doi.org/10.1137/0608024)
3. Bodlaender, H. L. and D. M. Thilikos. 1997. Treewidth for graphs with small chordality. Discrete Applied Mathematics, 79:45–61. [↗](https://doi.org/10.1016/s0166-218x(97)00031-0)
4. Catalan, Eugène. 1844. Note extraite d’une lettre adressée. Journal fürdie reine und angewandte Mathematik, 27:192. [find](https://scholar.google.com/scholar?q=Catalan%2C+Euge%CC%80ne%2E+1844%2E+Note+extraite+d%E2%80%99une+lettre+adresse%CC%81e%2E+Journal+fu%CC%88rdie+reine+und+angewandte+Mathematik%2C+27%3A192%2E)
5. Chiang, David. 2005. A hierarchical phrase-based model for statistical machine translation. In Proceedings of the 43rd Annual Conference of the Association for Computational Linguistics (ACL-05), pages 263–270, Ann Arbor, MI. (A.9) (A.10) [find](https://scholar.google.com/scholar?q=Chiang%2C+David%2E+2005%2E+A+hierarchical+phrase%2Dbased+model+for+statistical+machine+translation%2E+In+Proceedings+of+the+43rd+Annual+Conference+of+the+Association+for+Computational+Linguistics+%28ACL%2D05%29%2C+page) [our card](https://md.research.elamur.ai/free/papers/chiang-2005-hierarchical-phrase-based-model-statistical/)
6. Cormen, Thomas H., Charles E. Leiserson, and Ronald L. Rivest. 1990. Introduction to Algorithms. MIT Press, Cambridge, MA. [find](https://scholar.google.com/scholar?q=Cormen%2C+Thomas+H%2E%2C+Charles+E%2E+Leiserson%2C+and+Ronald+L%2E+Rivest%2E+1990%2E+Introduction+to+Algorithms%2E+MIT+Press%2C+Cambridge%2C+MA%2E)
7. Eisner, Jason. 2003. Learning non-isomorphic tree mappings for machine translation. In Proceedings of the 41st Meeting of the Association for Computational Linguistics, pages 205–208, Sapporo, Japan. [find](https://scholar.google.com/scholar?q=Eisner%2C+Jason%2E+2003%2E+Learning+non%2Disomorphic+tree+mappings+for+machine+translation%2E+In+Proceedings+of+the+41st+Meeting+of+the+Association+for+Computational+Linguistics%2C+pages+205%E2%80%93208%2C+Sapporo%2C+Japan%2E) [our card](https://md.research.elamur.ai/free/papers/eisner-2003-learning-non-isomorphic-tree-mappings/)
8. Galley, Michel, Mark Hopkins, Kevin Knight, and Daniel Marcu. 2004. What’s in a translation rule? In Proceedings of the 2004 Meeting of the North American chapter of the Association for Computational Linguistics (NAACL-04), pages 273–280, Boston, MA. [↗](https://doi.org/10.21236/ada460212) [our card](https://md.research.elamur.ai/free/papers/galley-2004-what-s-translation-rule/)
9. Gildea, Daniel and Daniel Štefankovič. 2007. Worst-case synchronous grammar rules. In Proceedings of the 2007 Meeting of the North American Chapter of the Association for Computational Linguistics (NAACL-07), pages 147–154, Rochester, NY. [find](https://scholar.google.com/scholar?q=Gildea%2C+Daniel+and+Daniel+S%CC%8Ctefankovic%CC%8C%2E+2007%2E+Worst%2Dcase+synchronous+grammar+rules%2E+In+Proceedings+of+the+2007+Meeting+of+the+North+American+Chapter+of+the+Association+for+Computational+Linguistics+%28)
10. Graham, Ronald. 1972. An efficient algorithm for determining the convex hull of a finite planar set. Information Processing Letters, 1:132–133. [find](https://scholar.google.com/scholar?q=Graham%2C+Ronald%2E+1972%2E+An+efficient+algorithm+for+determining+the+convex+hull+of+a+finite+planar+set%2E+Information+Processing+Letters%2C+1%3A132%E2%80%93133%2E)
11. Huang, Liang. 2007. Binarization, synchronous binarization, and target-side binarization. In Proceedings of the NAACL/AMTA Workshop on Syntax and Structure in Statistical Translation (SSST), pages 33–40, Rochester, NY. [find](https://scholar.google.com/scholar?q=Huang%2C+Liang%2E+2007%2E+Binarization%2C+synchronous+binarization%2C+and+target%2Dside+binarization%2E+In+Proceedings+of+the+NAACL%2FAMTA+Workshop+on+Syntax+and+Structure+in+Statistical+Translation+%28SSST%29%2C+pages+33%E2%80%93)
12. Huang, Liang and David Chiang. 2005. Better k-best parsing. In International Workshop on Parsing Technologies (IWPT05), pages 53–64, Vancouver. [find](https://scholar.google.com/scholar?q=Huang%2C+Liang+and+David+Chiang%2E+2005%2E+Better+k%2Dbest+parsing%2E+In+International+Workshop+on+Parsing+Technologies+%28IWPT05%29%2C+pages+53%E2%80%9364%2C+Vancouver%2E)
13. Huang, Liang, Hao Zhang, and Daniel Gildea. 2005. Machine translation as lexicalized parsing with hooks. In International Workshop on Parsing Technologies (IWPT05), pages 65–73, Vancouver. [find](https://scholar.google.com/scholar?q=Huang%2C+Liang%2C+Hao+Zhang%2C+and+Daniel+Gildea%2E+2005%2E+Machine+translation+as+lexicalized+parsing+with+hooks%2E+In+International+Workshop+on+Parsing+Technologies+%28IWPT05%29%2C+pages+65%E2%80%9373%2C+Vancouver%2E)
14. ISI Machine Translation Team. 2006. ISI at NIST-06. Working Notes of the NIST MT Evaluation Workshop, September. Washington, D.C. [find](https://scholar.google.com/scholar?q=ISI+Machine+Translation+Team%2E+2006%2E+ISI+at+NIST%2D06%2E+Working+Notes+of+the+NIST+MT+Evaluation+Workshop%2C+September%2E+Washington%2C+D%2EC%2E)
15. Knight, Kevin and Jonathan Graehl. 2005. An overview of probabilistic tree transducers for natural language processing. In Conference on Intelligent Text Processing and Computational Linguistics (CICLing), pages 1–24. Mexico City. [find](https://scholar.google.com/scholar?q=Knight%2C+Kevin+and+Jonathan+Graehl%2E+2005%2E+An+overview+of+probabilistic+tree+transducers+for+natural+language+processing%2E+In+Conference+on+Intelligent+Text+Processing+and+Computational+Linguistics+%28CICL)
16. Knuth, D. 1977. A generalization of Dijkstra’s algorithm. Information Processing Letters, 6(1):1–5. [↗](https://doi.org/10.1016/0020-0190(77)90002-3)
17. Liu, Yang, Qun Liu, and Shouxun Lin. 2005. Log-linear models for word alignment. In Proceedings of the 43rd Annual Conference of the Association for Computational Linguistics (ACL-05), pages 459–466, Ann Arbor, MI. [find](https://scholar.google.com/scholar?q=Liu%2C+Yang%2C+Qun+Liu%2C+and+Shouxun+Lin%2E+2005%2E+Log%2Dlinear+models+for+word+alignment%2E+In+Proceedings+of+the+43rd+Annual+Conference+of+the+Association+for+Computational+Linguistics+%28ACL%2D05%29%2C+pages+459%E2%80%93466%2C+)
18. Melamed, I. Dan. 2003. Multitext grammars and synchronous parsers. In Proceedings of the 2003 Meeting of the North American Chapter of the Association for Computational Linguistics (NAACL-03), pages 158–165, Edmonton. [find](https://scholar.google.com/scholar?q=Melamed%2C+I%2E+Dan%2E+2003%2E+Multitext+grammars+and+synchronous+parsers%2E+In+Proceedings+of+the+2003+Meeting+of+the+North+American+Chapter+of+the+Association+for+Computational+Linguistics+%28NAACL%2D03%29%2C+pages+1)
19. Mihalcea, Rada and Ted Pederson. 2003. An evaluation exercise for word alignment. In HLT-NAACL 2003 Workshop on Building and Using Parallel Texts: Data Driven Machine Translation and Beyond, pages 1–10, Edmonton. [find](https://scholar.google.com/scholar?q=Mihalcea%2C+Rada+and+Ted+Pederson%2E+2003%2E+An+evaluation+exercise+for+word+alignment%2E+In+HLT%2DNAACL+2003+Workshop+on+Building+and+Using+Parallel+Texts%3A+Data+Driven+Machine+Translation+and+Beyond%2C+pages+1%E2%80%931) [our card](https://md.research.elamur.ai/free/papers/mihalcea-2003-evaluation-exercise-word-alignment/)
20. Nederhof, M.-J. 2003. Weighted deductive parsing and knuth’s algorithm. Computational Linguistics, 29(1):135–144. [↗](https://doi.org/10.1162/089120103321337467)
21. Och, Franz Josef and Hermann Ney. 2004. The alignment template approach to statistical machine translation. Computational Linguistics, 30(4):417–449. [↗](https://doi.org/10.1162/0891201042544884)
22. Rambow, Owen and Giorgio Satta. 1999. Independent parallelism in finite copying parallel rewriting systems. Theoretical Computer Science, 223(1-2):87–120. [↗](https://doi.org/10.1016/s0304-3975(97)00190-4)
23. Rounds, William C. 1970. Mappings and grammars on trees. Mathematical Systems Theory, 4(3):257–287. [↗](https://doi.org/10.1007/bf01695769)
24. Satta, Giorgio and Enoch Peserico. 2005. Some computational complexity results for synchronous context-free grammars. In Proceedings of Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing (HLT/EMNLP), pages 803–810, Vancouver. [find](https://scholar.google.com/scholar?q=Satta%2C+Giorgio+and+Enoch+Peserico%2E+2005%2E+Some+computational+complexity+results+for+synchronous+context%2Dfree+grammars%2E+In+Proceedings+of+Human+Language+Technology+Conference+and+Conference+on+Empirical)
25. Schröder, E. 1870. Vier combinatorische Probleme. Zeitschrift für Mathematik und Physik, 15:361–376. [find](https://scholar.google.com/scholar?q=Schro%CC%88der%2C+E%2E+1870%2E+Vier+combinatorische+Probleme%2E+Zeitschrift+fu%CC%88r+Mathematik+und+Physik%2C+15%3A361%E2%80%93376%2E)
26. Shapiro, L. and A. B. Stephens. 1991. Bootstrap percolation, the Schröder numbers, and the n-kings problem. SIAM Journal on Discrete Mathematics, 4(2):275–280. [↗](https://doi.org/10.1137/0404025)
27. Shieber, Stuart M. 2004. Synchronous grammars as tree transducers. In Proceedings of the Seventh International Workshop on Tree Adjoining Grammar and Related Formalisms (TAG+ 7), pages 88–95, Vancouver. [find](https://scholar.google.com/scholar?q=Shieber%2C+Stuart+M%2E+2004%2E+Synchronous+grammars+as+tree+transducers%2E+In+Proceedings+of+the+Seventh+International+Workshop+on+Tree+Adjoining+Grammar+and+Related+Formalisms+%28TAG%2B+7%29%2C+pages+88%E2%80%9395%2C+Vancouve) [our card](https://md.research.elamur.ai/free/papers/shieber-2004-synchronous-grammars-as-tree-transducers/)
28. Shieber, Stuart and Yves Schabes. 1990. Synchronous tree-adjoining grammars. In Proceedings of the 13th International Conference on Computational Linguistics (COLING-90), volume III, pages 253–258, Helsinki. [find](https://scholar.google.com/scholar?q=Shieber%2C+Stuart+and+Yves+Schabes%2E+1990%2E+Synchronous+tree%2Dadjoining+grammars%2E+In+Proceedings+of+the+13th+International+Conference+on+Computational+Linguistics+%28COLING%2D90%29%2C+volume+III%2C+pages+253%E2%80%93258%2C+He) [our card](https://md.research.elamur.ai/free/papers/shieber-1990-synchronous-tree-adjoining-grammars/)
29. Wellington, Benjamin, Sonjia Waxmonsky, and I. Dan Melamed. 2006. Empirical lower bounds on the complexity of translational equivalence. In Proceedings of the International Conference on Computational Linguistics/Association for Computational Linguistics (COLING/ACL-06), pages 977–984, Sydney. [find](https://scholar.google.com/scholar?q=Wellington%2C+Benjamin%2C+Sonjia+Waxmonsky%2C+and+I%2E+Dan+Melamed%2E+2006%2E+Empirical+lower+bounds+on+the+complexity+of+translational+equivalence%2E+In+Proceedings+of+the+International+Conference+on+Computational)
30. Wu, Dekai. 1996. A polynomial–time algorithm for statistical machine translation. In 34th Annual Meeting of the Association for Computational Linguistics, pages 152–158, Santa Cruz, CA. [find](https://scholar.google.com/scholar?q=Wu%2C+Dekai%2E+1996%2E+A+polynomial%E2%80%93time+algorithm+for+statistical+machine+translation%2E+In+34th+Annual+Meeting+of+the+Association+for+Computational+Linguistics%2C+pages+152%E2%80%93158%2C+Santa+Cruz%2C+CA%2E)
31. Wu, Dekai. 1997. Stochastic inversion transduction grammars and bilingual parsing of parallel corpora. Computational Linguistics, 23(3):377–403. [find](https://scholar.google.com/scholar?q=Wu%2C+Dekai%2E+1997%2E+Stochastic+inversion+transduction+grammars+and+bilingual+parsing+of+parallel+corpora%2E+Computational+Linguistics%2C+23%283%29%3A377%E2%80%93403%2E) [our card](https://md.research.elamur.ai/free/papers/wu-1997-stochastic-inversion-transduction-grammars-bilingual/)
32. Zhang, Hao and Daniel Gildea. 2007. Factorization of synchronous context-free grammars in linear time. In NAACL Workshop on Syntax and Structure in Statistical Translation (SSST), pages 25–32, Rochester, NY. [find](https://scholar.google.com/scholar?q=Zhang%2C+Hao+and+Daniel+Gildea%2E+2007%2E+Factorization+of+synchronous+context%2Dfree+grammars+in+linear+time%2E+In+NAACL+Workshop+on+Syntax+and+Structure+in+Statistical+Translation+%28SSST%29%2C+pages+25%E2%80%9332%2C+Rochest)
33. Zhang, Hao, Liang Huang, Daniel Gildea, and Kevin Knight. 2006. Synchronous binarization for machine translation. In Proceedings of the NAACL, pages 256–263, New York. [find](https://scholar.google.com/scholar?q=Zhang%2C+Hao%2C+Liang+Huang%2C+Daniel+Gildea%2C+and+Kevin+Knight%2E+2006%2E+Synchronous+binarization+for+machine+translation%2E+In+Proceedings+of+the+NAACL%2C+pages+256%E2%80%93263%2C+New+York%2E)