The Weighted CFG Constraint

We introduce the weighted CFG constraint and propose a propagation algorithm that enforces domain consistency in $O(n^3\mathrm{\mid }G\mathrm{\mid })$ time. We show that this algorithm can be decomposed into a set of primitive arithmetic constraints without hindering propagation.