when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-141897
URL:

; ;

### Datalog-Expressibility for Monadic and Guarded Second-Order Logic

 pdf-format:

### Abstract

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.

### BibTeX - Entry

@InProceedings{bodirsky_et_al:LIPIcs.ICALP.2021.120,
author =	{Bodirsky, Manuel and Kn\"{a}uer, Simon and Rudolph, Sebastian},
title =	{{Datalog-Expressibility for Monadic and Guarded Second-Order Logic}},
booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
pages =	{120:1--120:17},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-195-5},
ISSN =	{1868-8969},
year =	{2021},
volume =	{198},
editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
}