Adding Circumscription to Decidable Fragments of First-Order Logic: A Complexity Rollercoaster

Carsten Lutz, Quentin Manière

We study extensions of expressive decidable fragments of first-order logic with circumscription, in particular the two-variable fragment FO${}^2$, its extension C${}^2$ with counting q…