Bag Context Tree Grammars

• Autorzy: Drewes F. , du Toit C. , Ewert S. , van der Merwe B. , van der Walt A.
• Języki publikacji: EN

Abstrakty

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.

Słowa kluczowe

EN

formal languages; tree grammars; regulated rewriting; bag context

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2008
• Tom: Vol. 86, nr 4
• Strony: 459--480
• Opis fizyczny: bibliogr. 11 poz.

Twórcy

autor

Drewes F.

autor

du Toit C.

autor

Ewert S.

autor

van der Merwe B.

autor

van der Walt A.

• School of Computer Science, University of the Witwatersrand, 2050 Wits, South Africa,

Bibliografia

• [1] Baker, B. S.: Composition of Top-Down and Bottom-Up Tree Transductions, Information and Control, 41, 1979, 186-213.
• [2] Dassow, J., Pǎun, G.: Regulated Rewriting in Formal Language Theory, Springer, Berlin, 1989.
• [3] Drewes, F.: Grammatical Picture Generation - A Tree-Based Approach, Texts in Theoretical Computer Science. An EATCS Series, Springer, 2006.
• [4] Drewes, F., Engelfriet, J.: Decidability of the Finiteness of Ranges of Tree Transductions, Information and Computation, 145, 1998, 1-50.
• [5] Drewes, F., Engelfriet, J.: Branching Synchronization Grammars with Nested Tables, Journal of Computer and System Sciences, 68, 2004, 611-656.
• [6] Drewes, F., van der Merwe, B.: Path Languages of rpc Tree Grammars are Regular, Fundamenta Informaticae, 82, 2008, 47-60.
• [7] Drewes, F., du Toit, C., Ewert, S., Högberg, J., van der Merwe, B., van der Walt, A.: Random Context Tree Grammars and Tree Transducers, South African Computer Journal, 34, 2005, 11-25.
• [8] Drewes, F., du Toit, C., Ewert, S., van der Merwe, B., van der Walt, A.: Bag Context Tree Grammars, Proc.10th Intl. Conf. on Developments in Language Theory (DLT 2006) (Z. Dang, O. Ibarra, Eds.), 4036, 2006, 226-237.
• [9] Ewert, S., van der Walt, A.: Random Context Picture Grammars, Publicationes Mathematicae (Debrecen), 54 (Supp), 1999, 763-786.
• [10] Fülöp, Z., Vogler, H.: Syntax-Directed Semantics: Formal Models Based on Tree Transducers, Springer, 1998.
• [11] Kruger, H., Ewert, S.: Translating Mutually Recursive Function Systems into Generalised Random Context Picture Grammars, South African Computer Journal, 36, 2006, 99-109.