technical contribution implies the decidability of order-invariance for ${\ensuremath{\mathrm{FO}^2}\xspace}$.

The satisfiability problem for ${\ensuremath{\mathrm{ESO}^2}\xspace}$ is decidable on the class of finite ordered $({\ensuremath{{S}}}_1,<_{1},<_{2})$-structures and on the class of finite ordered $({\ensuremath{{S}}}_{1},{\ensuremath{{S}}}_{2},<_{2})$-structures.

The first part in particular closes the gap between the decidability of ${\ensuremath{\mathrm{ESO}^2}\xspace}$ on ordered $<$-structures [@Otto01] and the undecidability of ${\ensuremath{\mathrm{EMSO}^2}\xspace}$ on ordered $(<_{1},<_{2},<_{3})$-structures [@Kieronski11]. More precisely we show that the decision problem can be solved in ${{{\ensuremath{\mbox{\sc 2-NExpTime}}\xspace}}}$ on $({\ensuremath{{S}}}_1, <_{1},<_{2})$-structures and as fast as the emptiness problem for multicounter automata on $({\ensuremath{{S}}}_{1},{\ensuremath{{S}}}_{2},<_{2})$-structures. We conjecture that there is an ${{\ensuremath{\mbox{\sc ExpSpace}}\xspace}}$-algorithm for the former problem. For proving our results we generalize techniques used in [@Manuel10], [@SchwentickZ10] and [@ManuelZ13]. In the course of this, a technique developed by Otto [@Otto01] for ${\ensuremath{\mathrm{ESO}^2}\xspace}$ on ordered $<$-structures turns out to be very valuable also for the more general structures considered here. We emphasize that while the basic techniques used for proving the results in this article are inspired by previous work, they are employed in a technically more demanding context.

As an introduction to the methods used for proving the technical main result, we show that ${\ensuremath{\mathrm{ESO}^2}\xspace}$ is ${{\ensuremath{\mbox{\sc NExpTime}}\xspace}}$-complete on finite $(<, {\ensuremath{{S}}})$-structures. This is also of some independent 