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

lmcs:1207 - Logical Methods in Computer Science, February 16, 2010, Volume 6, Issue 1 - https://doi.org/10.2168/LMCS-6(1:4)2010
Guarded Second-Order Logic, Spanning Trees, and Network FlowsArticle

Authors: Achim Blumensath

    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.


    Volume: Volume 6, Issue 1
    Published on: February 16, 2010
    Imported on: January 11, 2008
    Keywords: Computer Science - Logic in Computer Science,Computer Science - Discrete Mathematics,G.2.2,F.4.1

    Consultation statistics

    This page has been seen 930 times.
    This article's PDF has been downloaded 246 times.