On Spatial Conjunction as Second-Order Logic by Kuncak, Viktor, Rinard, Martin

“…We construct anembedding from first-order logic with spatial conjunction into second-order logic, and moresurprisingly, an embedding from full second order logic into first-order logic with spatialconjunction. …”
Get full text

On the Parameterized Intractability of Monadic Second-Order Logic by Stephan Kreutzer

“…One of Courcelle's celebrated results states that if C is a class of graphs of bounded tree-width, then model-checking for monadic second order logic (MSO_2) is fixed-parameter tractable (fpt) on C by linear time parameterized algorithms, where the parameter is the tree-width plus the size of the formula. …”
Get full text

On the Parameterised Intractability of Monadic Second−Order Logic by Kreutzer, S

Existential second−order logic over strings by Eiter, T, Gurevich, Y, Gottlob, G

Second Order Logic and the Weak Exponential Hierarchies by Gottlob, G, Leone, N, Veith, H

Existential Second−Order Logic over Strings by Eiter, T, Gottlob, G, Gurevich, Y

Monadic Second Order Logic with Measure and Category Quantifiers by Matteo Mio, Michał Skrzypczak, Henryk Michalewski

“…We investigate the extension of Monadic Second Order logic, interpreted over infinite words and trees, with generalized "for almost all" quantifiers interpreted using the notions of Baire category and Lebesgue measure.…”
Get full text

Characterizing Second Order Logic with First Order Quantifiers by Harel, David

“…It is shown that Q is equivalent in expressive power to second order logic by establishing the equivalence of alternating second order quantifiers and forming conjunctions of partially ordered first-order quantifiers.…”
Get full text

Pure Second-Order Logic with Second-Order Identity. by Paseau, A

On the Expressiveness of Frame Satisfiability and Fragments of Second−Order Logic by Eiter, T, Gottlob, G

On the decidability of monadic second-order logic with arithmetic predicates by Berthé, V, Karimov, T, Nieuwveld, J, Ouaknine, J, Vahanwala, M, Worrell, J

Guarded Second-Order Logic, Spanning Trees, and Network Flows by 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. …”
Get full text

The monadic second-order logic of graphs XVI : Canonical graph decompositions by Bruno Courcelle

“…This article establishes that the split decomposition of graphs introduced by Cunnigham, is definable in Monadic Second-Order Logic.This result is actually an instance of a more general result covering canonical graph decompositions like the modular decomposition and the Tutte decomposition of 2-connected graphs into 3-connected components. …”
Get full text

Complete Axiomatizations of Fragments of Monadic Second-Order Logic on Finite Trees by Amélie Gheerbrant, Balder ten Cate

“…We present axiomatizations of the monadic second-order logic (MSO), monadic transitive closure logic (FO(TC1)) and monadic least fixed-point logic (FO(LFP1)) theories of this class of structures. …”
Get full text

Second−Order Logic over Strings: Regular and Non−regular Fragments by Eiter, T, Gottlob, G, Schwentick, T

Existential second−order logic over graphs: Charting the tractability frontier by Gottlob, G, Kolaitis, P, Schwentick, T

Existential Second−Order Logic over Graphs: Charting the Tractability Frontier by Gottlob, G, Kolaitis, P, Schwentick, T

Expressing Cardinality Quantifiers in Monadic Second−Order Logic over Trees by Barany, V, Kaiser, L, Rabinovich, A

“…We study an extension of monadic second-order logic of order with the uncountability quantifier ``there exist uncountably many sets''. …”

Formal models of communicating systems : languages, automata, and monadic second-order logic / by 428469 Bollig, Benedikt

On the Union Closed Fragment of Existential Second-Order Logic and Logics with Team Semantics by Matthias Hoelzel, Richard Wilke

“…We present syntactic characterisations for the union closed fragments of existential second-order logic and of logics with team semantics. Since union closure is a semantical and undecidable property, the normal form we introduce enables the handling and provides a better understanding of this fragment. …”
Get full text