by Olivier Carton
Nous considérons ds automates aceptant des mots bi-infinis. Nous introduisons des automates non-ambigus où chaque mot accepté est l'étiquette d'exatement un chemin acceptant. Nous montrons que tout ensemble rationnel de mot bi-infinis est accepté par un tel automate. Ce résulat est l'analogue du théorème de McNaughton pour les mots bi-infinis.
We consider finite automata accepting bi-infinite words. We introduce unambiguous automata where each accepted word is the label of exactly one accepting path. We show that each rational set of bi-infinite words is accepted by such an automaton. This result is a counterpart of McNaughton's theorem for bi-infinite words.
PostScript Files