Bag context tree grammars

We introduce bag context, a device for regulated rewriting in tree grammars. Rather than being part of the developing tree, bag context (be) evolves on its own during a derivation. We show that the class of be 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 be tree languages is established. This result implies that the class of be tree languages is incomparable with the class of branching synchronization tree languages. © Springer-Verlag Berlin Heidelberg 2006.Conference Pape