72 citations · 368 across the 79 of their papers we have counts for
Showing 2010 · cs.CCShow all
3 papers · 2 filters
cs.CC2010★ 1 cited
Complexity of Existential Positive First-Order Logic
Manuel Bodirsky, Miki Hermann, Florian Richoux
Let gamma be a (not necessarily finite) structure with a finite relational signature. We prove that deciding whether a given existential positive sentence holds in gamma is in Logs…
cs.CC2010★ 2 cited
Schaefer's theorem for graphs
Manuel Bodirsky, Michael Pinsker
Schaefer's theorem is a complexity classification result for so-called Boolean constraint satisfaction problems: it states that every Boolean constraint satisfaction problem is eit…
cs.CC2010★ 9 cited
Distance Constraint Satisfaction Problems
Manuel Bodirsky, Victor Dalmau, Barnaby Martin +2
We study the complexity of constraint satisfaction problems for templates that are first-order definable in , the integers with the successor relation. Assuming…