A Dichotomy Theorem for Ordinal Ranks in MSO

Damian Niwiński, Paweł Parys, Michał Skrzypczak

We focus on formulae $\exists X.\phi (\vec{Y},X)$ of monadic second-order logic over the full binary tree, such that the witness $X$ is a well-founded set. The ordinal rank $\mathr…