%0 Thesis %1 Bloem96 %A Bloem, Roderick %C Leiden, The Netherlands %D 1996 %K transducers tree vari.TT %T Attribute Grammars and Monadic Second Order Logic %U ftp://ftp.wi.leidenuniv.nl/pub/CS/MScTheses/bloem.96.ps.gz %X It is shown that formulas in monadic second order logic (MSO) with one free variable can be mimicked by attribute grammars with a designated boolean attribute and vice versa. We prove that MSO formulas with two free variables have the same power in defining binary relations on nodes of a tree as regular path languages have. For graphs in general, MSO formulas turn out to be stronger. We also compare path languages against the routing languages of Klarlund and Schwartzbach. We compute the complexity of evaluating MSO formulas with free variables, especially in the case where there is a dependency between free variables of the formula. Last, it is proven that MSO tree transducers have the same strength as attributed tree transducers with the single use requirement and flags

@phdthesis{Bloem96, abstract = {It is shown that formulas in monadic second order logic (MSO) with one free variable can be mimicked by attribute grammars with a designated boolean attribute and vice versa. We prove that MSO formulas with two free variables have the same power in defining binary relations on nodes of a tree as regular path languages have. For graphs in general, MSO formulas turn out to be stronger. We also compare path languages against the routing languages of Klarlund and Schwartzbach. We compute the complexity of evaluating MSO formulas with free variables, especially in the case where there is a dependency between free variables of the formula. Last, it is proven that MSO tree transducers have the same strength as attributed tree transducers with the single use requirement and flags}, added-at = {2009-05-10T18:36:57.000+0200}, address = {Leiden, The Netherlands}, author = {Bloem, Roderick}, biburl = {https://www.bibsonomy.org/bibtex/2ce163441a779451e424832a1f500acf4/dparigot}, description = {Attribute Grammar}, interhash = {5f34672519d811da17a4d7b3153a6119}, intrahash = {ce163441a779451e424832a1f500acf4}, keywords = {transducers tree vari.TT}, month = {August}, school = {Leiden University}, timestamp = {2009-05-10T18:36:59.000+0200}, title = {Attribute Grammars and Monadic Second Order Logic}, url = {ftp://ftp.wi.leidenuniv.nl/pub/CS/MScTheses/bloem.96.ps.gz}, year = 1996 }