Regular languages of words over countable linear orderings

Abstract. We develop an algebraic model for recognizing languages of words indexed by countable linear orderings. This notion of recogniz-ability is effectively equivalent to definability in monadic second-order (MSO) logic. The proofs also imply the first known collapse result for MSO logic over countable linear orderings.