GUARDED SECOND-ORDER LOGIC, SPANNING TREES, AND NETWORK FLOWS
According to a theorem of Courcelle monadic second-order logic and guarded second-order logic (where one can also quantify over sets of edges) have the same expressive power over the class of all countable k-sparse hypergraphs. In the first part of the present paper we extend this result to hypergraphs of arbitrary cardinality. In the second part, we present a generalisation dealing with methods to encode sets of vertices by single vertices.
guarded second-order logic monadic second-order logic hypergraphs