interest. Previously, only the satisfiability problem for ${\ensuremath{\mathrm{EMSO}^2}\xspace}$ was known to be ${{\ensuremath{\mbox{\sc NExpTime}}\xspace}}$-complete on this class of structures. The extension of ${\ensuremath{\mathrm{ESO}^2}\xspace}$ with counting quantifiers was recently shown to be decidable on such structures, but only with very high complexity [@CharatonikW15].

Discussion {#discussion .unnumbered}
----------

Our results on satisfiability of ${\ensuremath{\mathrm{ESO}^2}\xspace}$ on finite ordered structures also help to make known results more robust, and therefore less vulnerable for confusion.

In work on two-variable first-logic originating from applications in verification and database theory often only unary relation symbols are allowed in formulas besides the linear orders and successors (see e.g. [@EtessamiVW02; @BojanczykDMSS11]). In most articles this restriction is stated clearly, or, at least the intended meaning is clear from the context. Yet abbreviations like ${\ensuremath{\mathrm{FO}^2}\xspace}(<)$ do not reflect this restriction. The arising ambiguity can lead to confusions for non-experts and readers only skimming an article. We definitely have been confused a couple of times, and we seem not be alone.

The second-order perspective taken in this article resolves this confusion. Furthermore, our results obviate the necessity to distinguish the two variants in the context of decidability of the finite satisfiability problem to some extent.

Outline {#outline .unnumbered}
-------

We introduce 