Bag context tree grammars

Drewes F. ; Toit C.D. ; Ewert S. ; Van Merwe B.D. ; Van Der Walt A.P.J. (2006)

Conference Paper

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.

Please refer to this item in SUNScholar by using the following persistent URL: http://hdl.handle.net/10019.1/12309
This item appears in the following collections: