Algorithm for reducing words in a Coxeter group Let $W$ be a Coxeter group with set of simple reflections $S$. Suppose that I have chosen a preferred reduced decomposition for every element of $W$. Given an arbitrary word in the alphabet $S$, is there an algorithm for reducing this word to my chosen decomposition using the Coxeter relations? That is to say, an algorithm which at each step replaces a subword of the form $s_i s_k s_i \dots$ by $s_k s_i s_k \dots$, or which removes an occurrence of $s_k^2$.
I would be happy with an answer in the following situation: $W=\Sigma_n$ is the symmetric group on $n$ letters and the preferred decomposition is given by taking the lexicographically smallest (or largest) reduced decomposition.
 A: An algorithm for reducing arbitrary words in any Coxeter group to their lexicographically least reduced representatives is described in the paper:
B. Brink and R.B. Howlett,
``A finiteness property and an automatic structure for Coxeter groups'',
Math. Ann. 296, (1993), 179-190.
It doesn't do exactly what you asked for, in that it doesn't do the reductions using only the defining Coxeter relations, but it uses longer substitutions, which can of course be derived from the defining relations, and are always length or lexicographically decreasing. It is the reduction algorithm based on the automatic structure of Coxeter groups, and runs in quadratic time in general. It has been implemented (for example) in the Computer Algebra System Magma.
A: Yes, at least if your chosen element is the lexicographically first reduced expression for your permutation.  This is how people usually prove that any two reduced expressions for a given permutation are connected by a series of long and short braid moves -- by reducing both to the lexicographically first reduced expression for that permutation.  
You can find such an algorithm for the symmetric group e.g. in:
Adriano Garsia, The saga of reduced factorizations of elements of the symmetric group, Publications du Laboratoire de Combinatoire et d' Informatique 29 (2002)
While oddly enough, I don't see this book listed on MathSciNet, I just found a copy available for free by googling: Adriano Garsia saga
This is also discussed (for more general Coxeter groups) in the book:
Anders Björner and Francesco Brenti, Combinatorics of Coxeter groups, Graduate Texts in Mathematics, 231, Springer, New York, 2005, xiv + 363 pp.
At least the connectedness result is there, and I believe it is again by this type of algorithm -- I don't have the book with me right now to check for sure.  
Another potentially relevant reference is:
Paul Edelman, Lexicographically first reduced words, Discrete Math, 147 (1995), no. 1-3, 95--106.
