The number of t-counters satisfying ||T || m ≤ n is O(n c G ), with c G = Since all of the other components in an item are bounded by O(n 4 ), there are polynomially (in n) many items that can be constructed for an input w. It is not difficult to see that each individual item can be constructed by a number of rule applications bounded by a polynomial as well.
the total number of applications of our deduction rules is also bounded by some polynomial in n. We thus conclude that the languages generated by the class TT-MCTAG are all included in PTIME.