and universal constraints. This is a simple generalization of the approach taken in [@SchwentickZ12].

We need the following notions. Let $T$ be a signature. A *unary $T$-type* is a maximally consistent conjunction of unary $T$-literals using variable $x$ only. A *(strictly) binary $T$-type* is a maximally consistent conjunction of binary $T$-literals using variables $x$ and $y$, where the conjunction includes the conjunct $x \neq y$. Each element of a structure has a unique unary $T$-type and each pair of elements has a unique binary $T$-type. If $\gamma$ is the binary type of $(a,b)$, then we denote the type of $(b,a)$ by $\bar \gamma$. The set of unary and binary $T$-types are denoted by $\Sigma_T$ and $\Gamma_T$.

A *constraint problem over $T$* is a tuple $C = (C_\exists,
C_\forall)$ where $C_\exists$ is a set of existential constraints and $C_\forall$ is a set of universal constraints. An [ *existential constraint*]{} $c_\exists$ is a tuple $(\sigma, E)$ where $\sigma \in \Sigma_T$ and $E\subseteq \Gamma_T \times \Sigma_T$. A structure with domain $D$ satisfies $c_\exists$ if for every element $a \in D$ of unary type $\sigma$ there is a $(\gamma, \tau) \in E$ and an element $b\in D$ of unary type $\tau$ such that $(a,b)$ 