Where first-order and monadic second-order logic coincide
From MaRDI portal
Publication:2986803
DOI10.1109/LICS.2012.37zbMATH Open1364.03015OpenAlexW2065443441WikidataQ130863238 ScholiaQ130863238MaRDI QIDQ2986803FDOQ2986803
Authors: Michael Elberfeld, Martin Grohe, Till Tantau 
Publication date: 16 May 2017
Published in: 2012 27th Annual IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1109/lics.2012.37
Recommendations
- Where first-order and monadic second-order logic coincide
- Expressivity and succinctness of order-invariant logics on depth-bounded structures
- On the Expressive Power of Graph Logic
- Succinctness of Order-Invariant Logics on Depth-Bounded Structures
- Expressive power of monadic logics on words, trees, pictures, and graphs
Cited In (15)
- Guarded second-order logic, spanning trees, and network flows
- Capturing MSO with one quantifier
- Algorithmic uses of the Feferman-Vaught theorem
- On low tree-depth decompositions
- First-order Logic with Connectivity Operators
- Recursive axiomatisations from separation properties
- A unified approach to structural limits and limits of graphs with bounded tree-depth
- Separating Graph Logic from MSO
- Where first-order and monadic second-order logic coincide
- Tree-depth, quantifier elimination, and quantifier rank
- Title not available (Why is that?)
- First-Order Logic with Connectivity Operators
- Forbidden induced subgraphs and the Łoś-Tarski theorem
- Expressivity and succinctness of order-invariant logics on depth-bounded structures
- Counting bounded tree depth homomorphisms
This page was built for publication: Where first-order and monadic second-order logic coincide
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2986803)
