A New Perspective on FO Model Checking of Dense Graph Classes
DOI10.1145/2933575.2935314zbMath1401.68196arXiv1805.01823MaRDI QIDQ4635873
Petr Hliněný, M. S. Ramanujan, Daniel Lokshtanov, Jan Obdržálek, Jakub Gajarský
Publication date: 23 April 2018
Published in: ACM Transactions on Computational Logic, 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/1805.01823
first-order logic; model checking; interpretations; fixed-parameter tractability; parameterized complexity; algorithmic metatheorems; bounded-degree graphs; sparse graph classes; FO logic; logic interpretations
68Q25: Analysis of algorithms and problem complexity
03B70: Logic in computer science
68Q60: Specification and verification (program logics, model checking, etc.)
05C75: Structural characterization of families of graphs