Affiliations: Department of Computing Science, Umeå
University, S-901 87 Umeå, Sweden. drewes@cs.umu.se | Department of Computer Science, University of
Stellenbosch, 7602 Stellenbosch, South Africa. cdutoit@cs.sun.ac.za | School of Computer Science, University of the
Witwatersrand, 2050 Wits, South Africa. sigrid.ewert@wits.ac.za | Department of Computer Science, University of
Stellenbosch, 7602 Stellenbosch, South Africa. abvdm@cs.sun.ac.za | Department of Computer Science, University of
Stellenbosch, 7602 Stellenbosch, South Africa. apjw@cs.sun.ac.za
Note: [] Address for correspondence: School of Computer Science,
University of the Witwatersrand, 2050 Wits, South Africa
Abstract: We introduce bag context as a device for regulated rewriting in tree
grammars. Bag context represents information that is not part of a developing
tree, but instead evolves separately during a derivation. We present several
results. First, we give some normal forms and equivalent formulations for bag
context tree grammars. Then we compare bag context tree grammars to their
random context counterparts. We show that bag context is strictly more powerful
than random context; in doing so, we show that the class of bag context tree
languages is the closure of the class of random context tree languages under
linear top-down tree transductions. Finally, we consider the structural
limitations of bag context tree grammars. We establish a necessary condition
for languages generated by bag context tree grammars, and use it to present a
tree language that cannot be generated by such a grammar. Moreover, we show
that the class of bag context tree languages is incomparable with the class of
branching synchronization tree languages.
Keywords: formal languages, tree grammars, regulated rewriting, bag context
