Upper Bounds on the Quantifier Depth for Graph Differentiation in First Order Logic

DOI10.1145/2933575.2933595zbMath1394.68162arXiv1605.03480OpenAlexW2964195552MaRDI QIDQ4635884

Sandra Kiefer, Pascal Schweitzer

Publication date: 23 April 2018

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

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

zbMATH Keywords

first-order logiccounting quantifiersWeisfeiler-Leman algorithmquantifier depthcolor refinement

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Logic with extra quantifiers and operators (03C80) Model theory of finite structures (03C13) Descriptive complexity and finite models (68Q19)

Related Items (1)

Unnamed Item

Uses Software

• nauty
• Traces
• bliss

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An optimal lower bound on the number of variables for graph identification
• Practical graph isomorphism. II.
• Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement
• Dimension Reduction via Colour Refinement
• Graphs Identified by Logics with Counting
• Conflict Propagation and Component Recursion for Canonical Labeling
• Logical complexity of graphs: a survey
• From Invariants to Canonization in Parallel
• Random Graph Isomorphism
• Universal Covers, Color Refinement, and Two-Variable Counting Logic: Lower Bounds for the Depth
• Near-Optimal Lower Bounds on Quantifier Depth and Weisfeiler--Leman Refinement Steps
• Graph isomorphism in quasipolynomial time [extended abstract]
• Fixed-point definability and polynomial time on graphs with excluded minors

This page was built for publication: Upper Bounds on the Quantifier Depth for Graph Differentiation in First Order Logic