Paper Info
Title
Semantical Evaluations as Monadic Second-Order Compatible Structure Transformations
Abstract
A transformation of structures 驴 is monadic second-order compatible (MS-compatible) if every monadic second-order property P can be effectively rewritten into a monadic second-order property Q such that, for every structure S, if T is the transformed structure 驴(S), then P(T) holds iff Q(S) holds.We will review Monadic Second-order definable transductions (MS-transductions): they are MS-compatible transformations of a particular form, i.e., defined by monadicsec ond-order (MS) formulas.The unfolding of a directed graph into a tree is an MS-compatible transformation that is not an MS-transduction.The MS-compatibility of various transformations of semantical interest follows. We will present three main cases and discuss applications and open problems.
Year
DOI
Venue
2002
10.1007/3-540-45931-6_1
FoSSaCS
Keywords
Field
DocType
monadic second-order definable transductions,various transformation,open problem,main case,iff q,ms-compatible transformation,monadicsec ond-order,monadic second-order property,semantical evaluations,monadic second-order compatible structure,particular form,semantical interest,directed graph
Transition system,Discrete mathematics,Knowledge representation and reasoning,Combinatorics,Tree (graph theory),Compatibility (mechanics),Directed graph,Graph rewriting,Monadic predicate calculus,Mathematics,Monad (functional programming)
Conference
Volume
ISSN
ISBN
2303
0302-9743
3-540-43366-X
Citations 
PageRank 
References 
0
0.34
10
Authors
1
Name
Order
Citations
PageRank
Bruno Courcelle13418388.00