by Olivier Carton
Nous introduisons une nouvelle variante des automates de Rabin pour lesquels la construction d'un automate pour l'union, l'intersection et le complément est très simple. De plus ces automates admettent une réduction naturelle de leur condition d'acceptation. Ceci conduit à une nouvelle caractérisation de l'indice de Rabin d'un ω-langage.
We introduce a new version of Rabin automata for which the construction of an automaton for the union, the intersection and the complement is very simple. Furthermore, these automata admit a natural reduction of their acceptance condition. This leads to a new characterization of the Rabin index of an ω-language.
PostScript File