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

DOI10.1007/978-3-662-44522-8_22zbMATH Open1407.03001OpenAlexW800522565MaRDI QIDQ2922020FDOQ2922020

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

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

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)

Cited In (11)

• 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
• Title not available (Why is that?)
• Computer Science Logic
• Order invariance on decomposable structures
• Where first-order and monadic second-order logic coincide
• Title not available (Why is that?)
• Where first-order and monadic second-order logic coincide
• A short tutorial on order-invariant first-order logic
• Counting bounded tree depth homomorphisms

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)