Bag context tree grammars
dc.contributor.author | Drewes F. | |
dc.contributor.author | Toit C.D. | |
dc.contributor.author | Ewert S. | |
dc.contributor.author | Van Merwe B.D. | |
dc.contributor.author | Van Der Walt A.P.J. | |
dc.date.accessioned | 2011-05-15T16:02:06Z | |
dc.date.available | 2011-05-15T16:02:06Z | |
dc.date.issued | 2006 | |
dc.description.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. | |
dc.description.version | Conference Paper | |
dc.identifier.citation | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | |
dc.identifier.citation | 4036 LNCS | |
dc.identifier.issn | 3029743 | |
dc.identifier.other | 10.1007/11779148_21 | |
dc.identifier.uri | http://hdl.handle.net/10019.1/12309 | |
dc.subject | Artificial intelligence | |
dc.subject | Computer science | |
dc.subject | Formal languages | |
dc.subject | Information technology | |
dc.subject | Synchronization | |
dc.subject | Theorem proving | |
dc.subject | Trees (mathematics) | |
dc.subject | Developing tree | |
dc.subject | Transductions | |
dc.subject | Tree grammars | |
dc.subject | Tree languages | |
dc.subject | Context free grammars | |
dc.title | Bag context tree grammars | |
dc.type | Conference Paper |