constraint $(\sigma, E)$. An element $b$ is a *$(\sigma, E)$-witness* of $a$ if there is a $(\gamma,\tau) \in E$, the element $b$ has unary type $\tau$ and $(a,b)$ has $T$-type $\gamma$. A *witness* of $a$ is an element that is a $(\sigma, E)$-witness for some existential constraint.

The following notations will be convenient for studying finite satisfiability of ${\ensuremath{\mathrm{ESO}^2}\xspace}$ on ordered structures. A constraint problem has a (finite) *$(<_{1},<_{2})$-solution* if it is solvable on the class of finite ordered $(<_{1},<_{2})$-structures. We use similar definitions for ${\ensuremath{\mathrm{ESO}^2}\xspace}({\ensuremath{{S}}}_1, {\ensuremath{{S}}}_2)$ and so on.

For a constraint problem over $O \cup T$ where $O$ is a subset of the symbols $<,<_1, <_2, \ldots$ and ${\ensuremath{{S}}}, {\ensuremath{{S}}}_1, {\ensuremath{{S}}}_2, \ldots$ we will denote existential and universal constraints in a slightly different fashion. To this end observe that all unary $O$-types are trivial (e.g. $x < x \wedge \lnot {\ensuremath{{S}}}(x,x)$) and can, without loss of generality, be omitted. Each binary $T \cup O$-type is a conjunction of a binary $O$-type and binary $T$-type. Therefore we can write existential constraints of constraint problems over $T \cup O$ as tuples $(\sigma, E)$ where $\sigma \in \Sigma_{T}$ and $E$ is a set of tuples $(d, \gamma, \tau)$ with $d \in 