Automata and cells in affine Weyl groups
Paul E. Gunnells · Representation Theory of the American Mathematical Society · 2010
Let W ~ \widetilde {W} be an affine Weyl group, and let C C be a left, right, or two-sided Kazhdan–Lusztig cell in W ~ \widetilde {W} . Let R e d ( C ) \mathtt {Red}(C) be the set of all reduced expressions of elements of C C , regarded as a formal language in the sense of the theory of computation. We show that R e d ( C ) \mathtt {Red}(C) is a regular language. Hence, the reduced expressions of the elements in any Kazhdan–Lusztig cell can be enumerated by a finite state automaton.