We will develop a BAR-HILLEL (Bar-Hillel et al., 1964) construction for STAG.
given a STAG G and a recognizable tree language L, we want to construct a STAG G such that In other words, we take the tree transformation τ G but additionally require the input tree to be in L. Consequently, this operation is also called input restriction.