Bag context tree grammars

Date
2006
Authors
Drewes F.
Toit C.D.
Ewert S.
Van Merwe B.D.
Van Der Walt A.P.J.
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
We introduce bag context, a device for regulated rewriting in tree grammars. Rather than being part of the developing tree, bag context (be) evolves on its own during a derivation. We show that the class of be 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 be tree languages is established. This result implies that the class of be tree languages is incomparable with the class of branching synchronization tree languages. © Springer-Verlag Berlin Heidelberg 2006.
Description
Keywords
Artificial intelligence, Computer science, Formal languages, Information technology, Synchronization, Theorem proving, Trees (mathematics), Developing tree, Transductions, Tree grammars, Tree languages, Context free grammars
Citation
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
4036 LNCS