Testing first-order properties for subclasses of sparse graphs

DOI10.1145/2499483zbMath1281.05114arXiv1109.5036WikidataQ57601367 ScholiaQ57601367MaRDI QIDQ5395732

Robin Thomas, Zdeněk Dvořák, Daniel Král'

Publication date: 17 February 2014

Published in: Journal of the ACM (Search for Journal in Brave)

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

zbMATH Keywords

tree-depth; first-order model checking; graphs with bounded expansion

Mathematics Subject Classification ID

68Q60: Specification and verification (program logics, model checking, etc.)

05C75: Structural characterization of families of graphs

03B10: Classical first-order logic