  A class of graph languages is definable in Monadic Second-Order logic (MSO)
if and only if it consists of sets of models of MSO formul{\ae}. If, moreover,
there is a computable bound on the tree-widths of the graphs in each such set,
the satisfiability and entailment problems are decidable, by Courcelle's
Theorem. This motivates the comparison of other graph logics to MSO. In this
paper, we consider the MSO definability of a Separation Logic of Relations
(SLR) that describes simple hyper-graphs, in which each sequence of vertices is
attached to at most one edge with a given label. Our logic SLR uses inductive
predicates whose recursive definitions consist of existentially quantified
separated conjunctions of relation and predicate atoms. The main contribution
of this paper is an expressive fragment of SLR that describes bounded
tree-width sets of graphs which can, moreover, be effectively translated into
MSO.
