Algebraic Characterization of FO for Scattered Linear Orderings
Alexis Bès, Olivier Carton · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2011
We prove that for the class of sets of words indexed by countable scattered linear orderings, there is an equivalence between definability in first-order logic, star-free expressions with marked product, and recognizability by finite aperiodic semigroups which satisfy some additional equation.