Successor-Invariant First-Order Logic on Classes of Bounded Degree

DOI10.1145/3373718.3394767zbMath1498.03069arXiv2009.11758OpenAlexW3032610015MaRDI QIDQ5145657

Julien Grange

Publication date: 21 January 2021

Published in: Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2009.11758

zbMATH Keywords

first-order logicfinite model theorysuccessor-invariance

Mathematics Subject Classification ID

Classical first-order logic (03B10) Model theory of finite structures (03C13) Interpolation, preservation, definability (03C40) Descriptive complexity and finite models (68Q19)

Cites Work

• Unnamed Item
• Unnamed Item
• Elements of finite model theory.
• On monadic NP vs monadic co-NP
• Expressivity and Succinctness of Order-Invariant Logics on Depth-Bounded Structures
• Towards a characterization of order-invariant queries over tame graphs
• Order Invariance on Decomposable Structures
• Deciding First-Order Properties of Nowhere Dense Graphs
• Successor-invariant first-order logic on finite structures
• Locality of order-invariant first-order formulas
• Order-Invariant First-Order Logic over Hollow Trees

This page was built for publication: Successor-Invariant First-Order Logic on Classes of Bounded Degree