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.



Algorithm for reducing words in a Coxeter group
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.


