Note that \({\mathcal {A}^{\prime }}_R^t\)  is of size that is polynomial in \(\mathcal {A}_R\)  and \(T_2\) . Since non emptiness of deterministic tree automata can be checked in polynomial time [1]}, the claim follows.
