Schützenberger and Eilenberg Theorems for Words on Linear Orderings

A journal version of this paper, with full proofs, has been published in JCSS.


In the case of finite words, a Schützenberger theorem proves that the star-free sets are exactly the languages recognized by finite aperiodic semigroups. This gives an algebraic characterization of star-free sets. The variety theorem of Eilenberg offers a general framework for the algebraic characterization of recognizable sets: it establishes a one-to-one correspondence between varieties of languages of finite words and pseudo-varieties of algebras. This paper contains extensions of those two well-known results to words on countable scattered linear orderings.



For copyright reasons I can not publish the final version of the paper here. Please send me an e-mail to get it. You may also find it here if your institution has access to the electronic ressources of Springer.

Valid HTML 4.01!