05840339

j

05840339 Gunnells, Paul E. Automata and cells in affine Weyl groups. Represent. Theory 14, 627-644, electronic only (2010). 2010 American Mathematical Society, Providence, RI EN Kazhdan-Lusztig cells finite state automata regular languages affine Weyl groups reduced expressions Coxeter hyperplane arrangements

doi:10.1090/S1088-4165-2010-00391-X

Summary: Let $\widetilde W$ be an affine Weyl group, and let $C$ be a left, right, or two-sided Kazhdan-Lusztig cell in $\widetilde W$. Let $\text{Red}(C)$ be the set of all reduced expressions of elements of $C$, regarded as a formal language in the sense of the theory of computation. We show that $\text{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.