umu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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.
Identifiers
URN: urn:nbn:se:umu:diva-21874ISBN: 0169-2968 OAI: oai:DiVA.org:umu-21874DiVA: diva2:212134
Note
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

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 33 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf