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…