by Olivier Carton
Dans un article précédent, nous avons introduit des automates pour les mots indexés par des ordres linéraires. Ces automates sont une généralisations des automates sur les mots transfinis introduits par Büchi. Dans ce papier, nous montrons que si on considère uniquement des mots indexés par des ordres dispersés, l'accessibilité dans ces automates peut être testé en temps nm2 où n et m sont le nombre d'états et le nombre de transitions de l'automates. Ceci résoud en particulier le problème pour les automates sur les mots transfinis.
In a preceding paper, automata have been introduced for words indexed by linear orderings. These automata are a generalization of automata on transfinite words introduced by Büchi. In these paper, we show that if only words indexed by scattered linear orderings are considered, the accessibility and the emptiness in these automata can be checked in time nm2 where n and m are the number of states and the number of transitions. This solves in particular the problem for automata on transfinite words.
PostScript of short version presented at the conference MFCS'2002 in Warszawa.