A particular interest has been in deciding the satisfiability problem for such extensions. Recently a decision procedure for the finite satisfiability problem for \(\mathrm {ESO}^2 \)  with one transitive relation and for \(\mathrm {ESO}^2 \)  with one partial order have been obtained [1]}. Previously \(\mathrm {ESO}^2 \)  with two equivalence relations [2]}, [3]} and \(\mathrm {ESO}^2 \)  with two “forest” relations have been shown to be decidable [4]}. While it is known that \(\mathrm {EMSO}^2 \)  with three equivalence relations is undecidable, this problem is still open for three “forest” relations. For \(\mathrm {ESO}^2 \)  with two linear orders, only a decision procedure for the finite satisfiability problem was known [5]}, [6]}. The satisfiability problem and the finite satisfiability problem for \(\mathrm {EMSO}^2 \)  is undecidable for three linear orders [7]}.
