Suppose we are given a group $G$ in terms of generators $t\_1, ..., t\_n$ which are order 2 in $S\_m$ (however we don't assume anything other than that these elements generate $G$ and have order 2). What is the most efficient way to determine:


1. If $G$ is abstractly isomorphic to a Coxeter group
2. Assuming yes, a Coxeter system for $G$
3. Assuming no, a presentation of $G$ as a quotient of a Coxeter group



Algorithm for root system of Coxeter group generated by permutations
There is a theoretical answer (as opposed to an algorithmic answer) found in Björner and Brenti's "Combinatorics of Coxeter groups", Section 1.5. (They seem to credit it to Matsumoto.) Their Theorem 1.5.1:


Suppose $W$ is a group generated by a subset $S$ consisting of elements of order $2$. Then TFAE:


1. $(W,S)$ is a Coxeter system (i.e. $S$ generates $W$ as a Coxeter group)
2. $(W,S)$ has the Exchange Property.
3. $(W,S)$ has the Deletion Property.


These are properties written in terms of reduced words.


To talk about an actual algorithm, we need a precise meaning to the assumption that "we are given a group $G$ in terms of generators $t\_1,\ldots,t\_n$". The only reasonable interpretation I'm finding for that is that we have an oracle that tells you whether two words in the generators stand for the same element.


In principle, you could design a "partial" algorithm, by checking Exchange or Deletion. But if your group is infinite, it might run forever, and you would never know whether your algorithm is about to come up with a counterexample to Exchange or Deletion.


EDIT: Now that I have noticed that the question specifies that all this takes place inside some symmetric group $S\_m$: The group $G$ is finite, so there are finitely many reduced words, and the Exchange Property can be checked in finite time.


