[Up]

Schützenberger and Eilenberg Theorems for Words on Linear Orderings

This paper is the journal version of a work presented at DLT'05.

Abstract

This paper contains extensions to words on countable scattered linear orderings of two well-known results of characterization of languages of finite words. We first extend a theorem of Schützenberger establishing that the star-free sets of finite words are exactly the languages recognized by finite aperiodic semigroups. This gives an algebraic characterization of star-free sets of words over countable scattered linear orderings. Contrarily to the case of finite words, first-order definable languages are strictly included into the star-free languages when countable scattered linear orderings are considered. Second, we extend the variety theorem of Eilenberg for finite words: there is a one-to-one correspondence between varieties of languages of words on countable scattered linear orderings and pseudo-varieties of algebras. The star-free sets are an example of such a variety of languages.

Keywords

Regular languages, rational languages, recognizable languages, infinite words, tranfinite words, linear orderings, star-free sets, first-order logic, varieties.

References

Download

For copyright reasons I can not publish the final version of the paper here. Please send me an e-mail to get it.

Valid HTML 4.01!