Blumensath, Achim - Guarded Second-Order Logic, Spanning Trees, and Network Flows

lmcs:1207 - Logical Methods in Computer Science, February 16, 2010, Volume 6, Issue 1
Guarded Second-Order Logic, Spanning Trees, and Network Flows

Authors: Blumensath, Achim

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.


Source : oai:arXiv.org:0910.3085
DOI : 10.2168/LMCS-6(1:4)2010
Volume: Volume 6, Issue 1
Published on: February 16, 2010
Submitted on: January 11, 2008
Keywords: Computer Science - Logic in Computer Science,Computer Science - Discrete Mathematics,G.2.2,F.4.1


Share

Consultation statistics

This page has been seen 38 times.
This article's PDF has been downloaded 17 times.