Expressivity and succinctness of order-invariant logics on depth-bounded structures

DOI10.1007/978-3-662-44522-8_22MaRDI QIDQ2922020zbMATH OpenOpenAlexFDO

Authors Kord Eickmeyer, Michael Elberfeld, Frederik Harwath

Publication date 14 October 2014

Published in Mathematical Foundations of Computer Science 2014 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-662-44522-8_22

zbMATH Keywords

first-order logicmonadic second-order logictree-depthexpressivitysuccinctnessorder-invariance

Mathematics Subject Classification ID

Classical first-order logic (03B10) Decidability of theories and sets of sentences (03B25)

Recommendations

• Succinctness of Order-Invariant Logics on Depth-Bounded Structures
• Order invariance on decomposable structures
• Towards a characterization of order-invariant queries over tame graphs
• Computer Science Logic
• Where first-order and monadic second-order logic coincide

Cited in

(11)

• Counting bounded tree depth homomorphisms
• Succinctness of Order-Invariant Logics on Depth-Bounded Structures
• Order-invariant MSO is stronger than counting MSO in the finite
• Towards a characterization of order-invariant queries over tame graphs
• scientific article; zbMATH DE number 458994 (Why is no real title available?)
• Computer Science Logic
• Order invariance on decomposable structures
• Where first-order and monadic second-order logic coincide
• scientific article; zbMATH DE number 7297889 (Why is no real title available?)
• Where first-order and monadic second-order logic coincide
• A short tutorial on order-invariant first-order logic

This page was built for publication: Expressivity and succinctness of order-invariant logics on depth-bounded structures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2922020)