3 papers
math.RA2026
The Network Satisfaction Problem for Relation Algebras with at most 4 Atoms
Manuel Bodirsky, Moritz Jahn, Simon Knäuer +2
Andréka and Maddux classified the relation algebras with at most 3 atoms, and in particular they showed that all of them are representable. Hirsch and Cristiani showed that the ne…
cs.LO2025
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…
math.LO2025
Network Satisfaction Problems Solved by k-Consistency
Manuel Bodirsky, Simon Knäuer
We show that the problem of deciding for a given finite relation algebra A whether the network satisfaction problem for A can be solved by the k-consistency procedure, for some nat…