Datalog-Expressibility for Monadic and Guarded Second-Order Logic

Manuel Bodirsky, Simon Knäuer, Sebastian Rudolph

We characterise the sentences in Monadic Second-order Logic (MSO) that are over finite structures equivalent to a Datalog program, in terms of an existential pebble game. We also s…