Let W be an infinite Coxeter group with a finite set S of generators. In this talk we will consider the set Red(W) of all reduced S-expressions of elements of W. Brink and Howlett showed that Red(W) is a "rational language" by constructing a finite state machine, or automaton, which accepts precisely the words of Red(W). Their construction, which we will recall, is based on properties of the generalized root system attached to W. We introduce a new family of automata which all recognize Red(W) and whose definition involves the weak order of W. We will also state two conjectures concerning the minimality of these automata. This is joint work with C. Hohlweg and N. Williams (LaCIM, UQàM, Montreal)