Drewes, Frank, du Toit, Christine, Ewert, Sigrid, van der Merwe, Brink and van der Walt, Andries (2008) Bag Context Tree Grammars. Fundamenta Informaticae, 86 (4). pp. 459-480. ISSN 0169-2968 (Print), 1875-8681 (Online)

Full text not available from this repository.

Abstract

We introduce bag context, a device for regulated rewriting in tree grammars. Rather than being part of the developing tree, bag context (bc) evolves on its own during a derivation. We show that the class of bc 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 bc tree languages is established. This result implies that the class of bc tree languages is incomparable with the class of branching synchronization tree languages.

Item Type:	Article
Additional Information:	[1] First published online: December 16, 2008. [2] Year issue published: 2008. [3] Published as: Fundamenta Informaticae, (2008), Vol. 86, (4), pp. 459–480. [4] Fundamenta Informaticae is the publication title of the Annales Societatis Mathematicae Polonae (Polish Mathematical Society) published under the auspices of the European Association for Theoretical Computer Science (EATCS).
Uncontrolled Keywords:	formal languages, tree grammars, regulated rewriting, bag context
Subjects:	Q Science > QA Mathematics > QA76 Computer software
Pre-2014 Departments:	School of Computing & Mathematical Sciences
Related URLs:	Publisher Publisher Organisation
Last Modified:	05 Nov 2019 13:51
URI:	http://gala.gre.ac.uk/id/eprint/10099

Actions (login required)

View Item