Where first-order and monadic second-order logic coincide

DOI10.1109/LICS.2012.37MaRDI QIDQ2986803zbMATH OpenOpenAlexWikidataFDO

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

zbMATH Keywords

first-order logicgraph classesmonadic second-order logictree depthguarded second-order logic

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Classical first-order logic (03B10)

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)

• Recursive axiomatisations from separation properties
• Capturing MSO with one quantifier
• Forbidden induced subgraphs and the Łoś-Tarski theorem
• Separating Graph Logic from MSO
• On low tree-depth decompositions
• Guarded second-order logic, spanning trees, and network flows
• A unified approach to structural limits and limits of graphs with bounded tree-depth
• Algorithmic uses of the Feferman-Vaught theorem
• scientific article; zbMATH DE number 7029306 (Why is no real title available?)
• Where first-order and monadic second-order logic coincide
• Tree-depth, quantifier elimination, and quantifier rank
• First-order Logic with Connectivity Operators
• Counting bounded tree depth homomorphisms
• Expressivity and succinctness of order-invariant logics on depth-bounded structures
• First-Order Logic with Connectivity Operators

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)