We compare, in terms of expressive power, two notions of automata recognizing finite N-free pomsets: branching automata by Lodaya and Weil [Lodaya and Weil, 1998; Lodaya and Weil, 1998; Lodaya and Weil, 2000; Lodaya and Weil, 2001] and pomset automata by Kappé, Brunet, Luttik, Silva and Zanasi [Kappé et al., 2018]. In the general case, they are equivalent. We also consider sub-classes of both kind of automata that we prove equivalent.

Several definitions of automata on words indexed by ordinals have been proposed previously. The first one was introduced by Büchi 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 for α < ω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.