cHAIN aUTOMATA

Olivier Carton

IBP-Litp 1994/02: Rapport de Recherche Litp / Litp research reports
16 pages - Décembre/December 1994 - Document en anglais.

PostScript : Ko /Kb

Titre / Title: cHAIN aUTOMATA

Résumé : Nous introduisons une nouvelle classe d'automates de Rabin pour lesquels la construction d'un automate reconnaissant l'union, l'intersection et le complémentaire 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 w-langage.

Abstract : 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. Futhermore, these automata admit a natural reduction of their acceptance condition. This leads to a new characterization of the Rabin index of an w-language.

Publications internes Litp 1994 / Litp research reports 1994