First-Order Logic with Counting: EF-games and Model-Checking on Monadically Stable Classes

We demonstrate that the model-checking problem for first-order logic with modulo counting quantification (FO+Mod) is fixed-parameter tractable on monadically stable classes of graphs. These classes extend the concepts of nowhere dense and structurally nowhere dense classes. A significant contribution of our work is the characterization of FO+Mod, as well as the more general counting logic FO(P), through an Ehrenfeucht-Fraïssé game, which we believe holds independent interest. By carefully adapting the techniques developed by Dreier, Mählmann, and Siebertz (2023), we are working towards achieving the desired results. This is ongoing work, joint with Peter Rossmanith.

Authors

• Daniel Mock

Keywords

No keywords are indexed for this paper.