2026-08-16T23:28:15Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14189 2024-03-06T10:53:42Z ddc:004 open_access

Datalog-Expressibility for Monadic and Guarded Second-Order Logic Bodirsky, Manuel Knäuer, Simon Rudolph, Sebastian Monadic Second-order Logic Guarded Second-order Logic Datalog constraint satisfaction homomorphism-closed conjunctive query primitive positive formula pebble game ω-categoricity 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 show that for every class C of finite structures that can be expressed in MSO and is closed under homomorphisms, and for all 𝓁,k ∈ , there exists a canonical Datalog program Π of width (𝓁,k), that is, a Datalog program of width (𝓁,k) which is sound for C (i.e., Π only derives the goal predicate on a finite structure 𝔄 if 𝔄 ∈ C) and with the property that Π derives the goal predicate whenever some Datalog program of width (𝓁,k) which is sound for C derives the goal predicate. The same characterisations also hold for Guarded Second-order Logic (GSO), which properly extends MSO. To prove our results, we show that every class C in GSO whose complement is closed under homomorphisms is a finite union of constraint satisfaction problems (CSPs) of ω-categorical structures. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Manuel Bodirsky and Simon Knäuer and Sebastian Rudolph 2021 Is Part Of LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2021.120 urn:nbn:de:0030-drops-141897 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.120 eng https://creativecommons.org/licenses/by/4.0/legalcode