By storing partially completed arcs in the chart and interleaving the inner two loops, complexity of O(|T |n 3 m!2 m ) can be achieved.
while the algorithm is exponential in m, the fan-out of the grammar, it is polynomial in the size of the input string.