First-order separation over countable ordinals
Thomas Colcombet, Sam van Gool, Rémi Morvan · Lecture notes in computer science · 2022
Abstract 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 Almeida on finite words, and of Place and Zeitoun on $$\omega $$ ω -words. For this, we develop the algebraic concept of monoid (resp. $$\omega $$ ω -semigroup, resp. ordinal monoid) with aperiodic merge, an extension of monoids (resp. $$\omega $$ ω -semigroup, resp. ordinal monoid) that explicitly includes a new operation capturing the loss of precision induced by first-order indistinguishability. We also show the computability of FO-pointlike sets, and the decidability of the covering problem for first-order logic on countable ordinal words.