The monadic second-order logic of graphs VII: graphs as relational structures

AbstractRelational structures form a unique framework in which various types of graphs and hypergraphs can be formalized and studied. We define operations on structures that are compatible with monadic second-order logic, and that are powerful enough to represent context-free graph and hypergraph grammars of various types, namely, the so-called hyperedge replacement, C-edNCE, and separated handle rewriting grammars. Several results concerning monadic second-order properties of the generated sets are obtained in a uniform way.We also give a logical characterization of the equational sets of structures that generalizes the ones obtained by Engelfriet and Courcelle for hyperedge replacement and C-edNCE sets of graphs