Logic over words on countable ordinals

Copyright informations

This material has been published in Journal of Computer and System Science, vol. 63, n. 3, pp 394-431, Nov. 2001, the only definitive repository of the content that has been certified and accepted after peer review. Copyright and all rights therein are retained by Academic Press. This material may not be copied or reposted without explicit permission. IDEAL


The main result of this paper is the extension of the theorem of Schützenberger, McNaughton and Papert on star-free sets of finite words to languages of words of countable length. We also give an other proof of the theorem of Büchi which establishes the equivalence between automata and monadic second-order sentences for defining sets of words of denumerable length.



Gzipped postscript file (160 Ko)

Valid HTML 4.01!