×

Ensembles reconnaissables de mots biinfinis. (French) Zbl 0589.68056

Can. J. Math. (to appear).
We introduce the notion of recognizability by a finite automaton for sets of two sided infinite words. It extends the corresponding notion for one sided infinite words studied by R. Büchi and R. McNaughton. Our main result is a generalization of McNaughton’s theorem about determinism of automata on infinite words. The result states that the family of recognizable sets of two-sided infinite words is the Boolean closure of the family of sets recognized by deterministic automata.

MSC:

68Q45 Formal languages and automata