|
| << vorige | volgende >> |
Tijdschrift beschrijving
Alle jaargangen van het bijbehorende tijdschrift
Alle afleveringen van het bijbehorende jaargang
Alle artikelen van de bijbehorende aflevering
Details van artikel 2 van 7 gevonden artikelen
| Titel: |
Bag Context Tree Grammars |
| Auteur: |
Drewes, Frank du Toit, Christine Ewert, Sigrid van der Merwe, Brink van der Walt, Andries |
| Verschenen in: |
Fundamenta informaticae |
| Paginering: | Jaargang 86 (2008) nr. 4 pagina's 459-480 |
| Jaar: |
2008-12-16 |
| Inhoud: |
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. |
| Uitgever: |
IOS Press |
| Bronbestand: |
Elektronische Wetenschappelijke Tijdschriften |
Details van artikel 2 van 7 gevonden artikelen
| << vorige | volgende >> |