6 citations · 9 across the 9 of their papers we have counts for
3 papers · 1 filter
A New Perspective on FO Model Checking of Dense Graph Classes
Jakub Gajarský, Petr Hliněný, Daniel Lokshtanov +2
We study the first-order (FO) model checking problem of dense graphs, namely those which have FO interpretations in (or are FO transductions of) some sparse graph classes. We give…
Strong Backdoors for Linear Temporal Logic
Arne Meier, Sebastian Ordyniak, M. S. Ramanujan +1
In the present paper we introduce the notion of strong backdoors into the field of temporal logic for the CNF-fragment of linear temporal logic introduced by Fisher. We study the p…
FO Model Checking on Posets of Bounded Width
Jakub Gajarský, Petr Hliněný, Daniel Lokshtanov +4
Over the past two decades the main focus of research into first-order (FO) model checking algorithms have been sparse relational structures-culminating in the FPT-algorithm by Groh…