Finite automata and ordinals

Copyright informations

This material has been published in Theoretical Computer Science, vol. 156, pp 119-144, Mars 1996. Copyright and all rights therein are retained by Elsevier. This material may not be copied or reposted without explicit permission.

Read this to learn more about publisher's official green light to self-archive both their pre-refereeing preprints and their refereed postprints.


Several definitions of automata on words indexed by ordinals have been proposed previously. The first one was introduced by Buchi to prove the decidability of the monadic second order theory of denumerable ordinals. Wojciechowski studied the properties of these automata independently of the length of the input. The second definition, proposed by Choueka, works only on words of length less than ω^n. In this paper, we restrict the domain of Wojciechowski automata to the domain of Choueka's ones (that is, given n<ω, we keep only sequences of length less than ω^(n+1) in the language defined by a Wojciechowski automaton) in order to prove the equivalence between Choueka automata and Wojciechowski automata. Then, we obtain the closure under complementation of the class of Wojciechowski's definable sets, and finally we give an algorithm for determinizing Wojciechowski automata.



Gzipped postcript format

Valid HTML 4.01!