The kernel computational complexity is , where all pairwise comparisons are carried out between T 1 and T 2 .
there are fast algorithms for kernel computation that run in linear time on average, either by dynamic programming (Collins and Duffy, 2002), or pre-sorting production rules before training (Moschitti, 2006).