Logic over Words on Denumerable Ordinals

摘要

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 another 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.