Bag context tree grammars

Simple item page
dc.contributor.authorDrewes F.
dc.contributor.authorToit C.D.
dc.contributor.authorEwert S.
dc.contributor.authorVan Merwe B.D.
dc.contributor.authorVan Der Walt A.P.J.
dc.date.accessioned2011-05-15T16:02:06Z
dc.date.available2011-05-15T16:02:06Z
dc.date.issued2006
dc.description.abstractWe 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.versionConference Paper
dc.identifier.citationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
dc.identifier.citation4036 LNCS
dc.identifier.issn3029743
dc.identifier.other10.1007/11779148_21
dc.identifier.urihttp://hdl.handle.net/10019.1/12309
dc.subjectArtificial intelligence
dc.subjectComputer science
dc.subjectFormal languages
dc.subjectInformation technology
dc.subjectSynchronization
dc.subjectTheorem proving
dc.subjectTrees (mathematics)
dc.subjectDeveloping tree
dc.subjectTransductions
dc.subjectTree grammars
dc.subjectTree languages
dc.subjectContext free grammars
dc.titleBag context tree grammars
dc.typeConference Paper
Files
Collections
Stellenbosch University - Scopus Publications