We introduce bag context, a device for regulated rewriting in tree and string grammars. Rather than being part of the developing tree or string, bag context (bc) evolves on its own during a derivation. We show that the class of bc tree languages
is the closure of the class of random context tree languages under linear top-down tree transductions. Further, an interchange theorem for subtrees of dense trees in bc tree languages is established. This result implies that the class of bc tree languages is incomparable with the class of branching synchronization tree languages.
Key words: regulated rewriting; tree languages; random context
