First-order separation over countable ordinals

Thomas Colcombet, Sam van Gool, Rémi Morvan

We show that the existence of a first-order formula separating two monadic second order formulas over countable ordinal words is decidable. This extends the work of Henckell and Al…