Regular Languages of Words Over Countable Linear Orderings
Olivier Carton, Thomas Colcombet · 2011
Abstract. We develop an algebraic model suitable for recognizing lan-guages of words indexed by countable linear orderings. We prove that this notion of recognizability is e↵ectively equivalent to definability in monadic second-order (MSO) logic. This reproves in particular the de-cidability of MSO logic over the rationals with order. Our proof also implies the first known collapse result for MSO logic over countable lin-ear orderings. 1