Deciding First-Order Properties of Nowhere Dense Graphs
From MaRDI portal
Publication:4640289
DOI10.1145/3051095zbMath1426.68172arXiv1311.3899MaRDI QIDQ4640289
Stephan Kreutzer, Sebastian Siebertz, Martin Grohe
Publication date: 17 May 2018
Published in: Journal of the ACM, Proceedings of the forty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1311.3899
68R10: Graph theory (including graph drawing) in computer science
68Q60: Specification and verification (program logics, model checking, etc.)
05C75: Structural characterization of families of graphs
03B25: Decidability of theories and sets of sentences
68Q19: Descriptive complexity and finite models
05C57: Games on graphs (graph-theoretic aspects)
05C42: Density (toughness, etc.)
Uses Software