Change search
ReferencesLink to record
Permanent link

Direct link
Bag Context Tree Grammars
Umeå University, Faculty of Science and Technology, Departement of Computing Science.
Show others and affiliations
2008 (English)In: Fundamenta Informaticae, Vol. 86, no 4, 459-480 p.Article in journal (Refereed) Published
Abstract [en]

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.

Place, publisher, year, edition, pages
2008. Vol. 86, no 4, 459-480 p.
URN: urn:nbn:se:umu:diva-21874ISBN: 0169-2968OAI: diva2:212134
Drewes, Frank du Toit, Christine Ewert, Sigrid van der Merwe, Brink van der Walt, AndriesAvailable from: 2009-04-21 Created: 2009-04-21 Last updated: 2009-04-21

Open Access in DiVA

No full text

Other links

<Go to ISI>://000262368100006
By organisation
Departement of Computing Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 30 hits
ReferencesLink to record
Permanent link

Direct link