our notation and basic tool set in Section \[section:preliminaries\]. In Section \[section:warm-up\] we present two different ideas for deciding ${\ensuremath{\mathrm{ESO}^2}\xspace}$ on finite $(<,{\ensuremath{{S}}})$-structures. These ideas are generalized to finite ordered $({\ensuremath{{S}}}_1, <_{1},<_{2})$-structures and finite ordered $({\ensuremath{{S}}}_1, {\ensuremath{{S}}}_{2},<_{2})$-structures in Sections \[section:twoorders\] and \[section:twosuccessors\]. We discuss order-invariance in Section \[section:invariance\]. We conclude in Section \[section:conclusion\].

Preliminaries {#section:preliminaries}
=============

In this section we introduce ordered structures and two-variable logic.

Ordered Structures {#sec:ordered-structures}
------------------

In this article we consider logical formulas that are interpreted over *ordered* structures, i.e. relational structures where some relation symbols are interpreted by linear orders and their corresponding successor relations. We assume that all structures are *finite* structures with a *non-empty domain*.

A [*linear order*]{} $<$ is a transitive, total and antisymmetric relation, that is, $a  <  b$ and $b  <  c$ implies $a < c$ ; $a <  b $ or $b  <  a$ holds; and not both $a  <  b$ and $b  <  a$ are satisfied at the same time for all elements $a, b$ and $c$. The *induced successor relation* ${\ensuremath{{S}}}$ of a linear order $ < $ contains a tuple $(a, b)$ if $a <  b$ and there is no element $c$ such that $a <  