Therefore, the FO logic of MSCs can be considered a canonical specification language for such systems. Unfortunately, its study turned out to be difficult, since algebraic and automata-theoretic approaches that work for words, trees, or Mazurkiewicz traces do not carry over. In particular, until now, the following central problem remained open:

Partial answers were given for CFMs with bounded channel capacity [@HenriksenJournal; @Kuske01; @GKM06] and for fragments of FO that restrict the logic to bounded-degree predicates [@BolligJournal] or to two variables [@BFG-stacs18].

In this paper, we answer the general question positively. To do so, we make a detour through a variant of propositional dynamic logic (PDL) with loop and converse [@FisL79; @Streett81]. Actually, we introduce *star-free* PDL, which serves as an interface between FO logic and CFMs. That is, there are two main tasks to accomplish:

-   Translate every FO sentence into a star-free PDL sentence.

-   Translate every star-free PDL sentence into a CFM.

Both parts constitute results of own interest. In particular, step (i) implies that, over MSCs, FO logic has the three-variable property, i.e., every FO sentence over MSCs can be rewritten into one that uses only three different variable names. Note that this is already interesting 