R. Bloem. Leiden University, Leiden, The Netherlands, (августа 1996)
Аннотация
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
%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
}