Codeterministic automata on infinite words (Q1061501)

It is known that, contrary to the case of finite words, not all sets of infinite words recognizable by a finite automaton (Büchi's condition) can be accepted by a deterministic one. It is proved in this paper that any recognizable set of infinite words can be recognized by some finite codeterministic automaton. Codeterministic automata can be considered as reverse deterministic automata reading an infinite word from infinity to the beginning.