Guarded second-order logic, spanning trees, and network flows
A Blumensath - Logical Methods in Computer Science, 2010 - lmcs.episciences.org
Logical Methods in Computer Science, 2010•lmcs.episciences.org
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.
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.
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 -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.
lmcs.episciences.org