In Elements of Finite Model Theory, page 11, there's the following exercise that I haven't been able to solve after several attempts:
For a string $s = s_1 s_2 ... s_n$ (over the lowercase latin alphabet), $M_s$ is a structure with universe $\{1, 2, ..., n\}$ (corresponding to positions in the string), a binary relation $<$ with the usual meaning, and unary relations $A, B, ..., Z$ such that $D(i)$ iff $s_i = d$ and so on. For example $M_{abba}$ has universe $\{1,2,3,4\}$, with $A$ interpreted as $\{1, 4\}$, $B$ as $\{2,3\}$ and the rest would be empty relations.
Let $\Phi$ be a monadic second-order logic sentence over strings. Show how to construct a sentence (*)$\Psi$ such that $M_s \models \Psi$ iff there is a string $s'$ such that $|s| = |s'|$ and $M_{s \cdot s'} \models \Phi$. Here $|s|$ refers to the length of $s$, and $s \cdot s'$ is the concatenation of $s$ and $s'$.
(*) refers to an MSO sentence as well, otherwise the exercise wouldn't make much sense. I know how to do it passing through DFA's, as I know how to build a DFA for $\frac{1}{2}L$ from a DFA for $L$. But Büchi's theorem is proven in Chap. 7, and therefore that shouldn't be the intended solution.