Existential MSO over two successors is strictly weaker than over linear orders

As is well-known a language of finite words, considered as labeled linear orders, is defin-able in monadic second-order logic (MSO) iff it is definable in the existential fragment of MSO, that is the quantifier alternation hierarchy collapses. Even more, it does not make a difference if we consider existential MSO over a linear order or a successor relation only. In this note we show that somewhat surprisingly the latter does not hold if we just add a second linear order and consider finite relational structures with two linear orders, so-called texts. Key words: existential monadic second-order logic, Ehrenfeucht-Fräısse ́ game, Ajtai-Fagin game, texts, successor structures 1