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

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

Pascal Schweitzer, Sandra Kiefer

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 logic; counting quantifiers; Weisfeiler-Leman algorithm; quantifier depth; color refinement

Mathematics Subject Classification ID

05C85: Graph algorithms (graph-theoretic aspects)

03C80: Logic with extra quantifiers and operators

03C13: Model theory of finite structures

68Q19: Descriptive complexity and finite models

Uses Software

• nauty
• Traces
• bliss