Showing math.RAShow all
3 papers · 1 filter
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…
math.RA2026
Symmetric Linear Arc Monadic Datalog and Gadget Reductions
Manuel Bodirsky, Florian Starke
A Datalog program solves a constraint satisfaction problem (CSP) if and only if it derives the goal predicate precisely on the unsatisfiable instances of the CSP. There are three D…
math.RA2026
Conservative Maltsev Constraint Satisfaction Problems
Manuel Bodirsky, Andrew Moorhead
One of the central open problems to classify the computational complexity of finite-domain constraint satisfaction problems within P is to prove better algorithmic results for CSPs…