72 citations · 368 across the 79 of their papers we have counts for
Showing 2020 · cs.LOShow all
2 papers · 2 filters
cs.LO2020
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…
cs.LO2020
ASNP: a tame fragment of existential second-order logic
Manuel Bodirsky, Simon Knäuer, Florian Starke
Amalgamation SNP (ASNP) is a fragment of existential second-order logic that strictly contains binary connected MMSNP of Feder and Vardi and binary guarded monotone SNP of Bienvenu…