2022/01/09 by Thomas Colcombet, Colcombet, Thomas, Sam van Gool +3 · 1 citation
Computer Science · #Advanced Algebra and Logic #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Logic in Computer Science (cs.LO) #Logic, Reasoning, and Knowledge #semigroups and automata theory
paper · doi:10.48550/arxiv.2201.03089
openalex publication_date 2022/01/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 ω-words. For this, we develop the algebraic concept of monoid (resp. ω-semigroup, resp. ordinal monoid) with aperiodic merge, an extension of monoids (resp. ω-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.