Nivat, Maurice; Perrin, Dominique 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. Cited in 4 Documents MSC: 68Q45 Formal languages and automata Keywords:recognizability by a finite automaton; two sided infinite words; deterministic automata PDFBibTeX XML