Upper Bounds on the Quantifier Depth for Graph Differentiation in First Order Logic
From MaRDI portal
Publication:4635884
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
first-order logic; counting quantifiers; Weisfeiler-Leman algorithm; quantifier depth; color refinement
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