Solving the enumeration and word problems on Coxeter groups

The word problem and indeed the enumeration problem in Coxeter groups are intractable in most cases. A direct way to solve the enumeration problem is by listing the canonical representatives of the equivalence classes, but this entails to solve the word problem for certain pairs of words in the group. We describe two methods to solve these problems and we analyze their complexity. We characterize two particular types of groups in which the word and the enumeration problems can efficiently be solved.