A CYK+ Variant for SCFG Decoding Without a Dot Chart

Research output: Chapter in Book/Report/Conference proceedingConference contribution


While CYK+ and Earley-style variants are popular algorithms for decoding unbinarized SCFGs, in particular for syntax-based Statistical Machine Translation, the algorithms rely on a so-called dot chart which suffers from a high memory consumption. We propose a recursive variant of the CYK+ algorithm that eliminates the dot chart, without incurring an increase in time complexity for SCFG decoding. In an evaluation on a string-to-tree SMT scenario, we empirically demonstrate substantial improvements in memory consumption and translation speed.
Original languageEnglish
Title of host publicationProceedings of SSST-8, Eighth Workshop on Syntax, Semantics and Structure in Statistical Translation
Place of PublicationDoha, Qatar
PublisherAssociation for Computational Linguistics
Number of pages9
Publication statusPublished - 1 Oct 2014


Dive into the research topics of 'A CYK+ Variant for SCFG Decoding Without a Dot Chart'. Together they form a unique fingerprint.

Cite this