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.

I don't think this is what the questioner means, so this is not really an answer. But it's worth mentioning and it's too long for a comment.

If we know that $t_1,\ldots,t_n$ are transpositions, then $G$ is a "reflection subgroup" of $S_m$ (a subgroup generated by reflections). Then a theorem of Deodhar ("A note on subgroups generated by reflections in Coxeter groups") and Dyer ("Reflection subgroups of Coxeter systems") tells us that $G$ is a Coxeter group. They also give a recipe for finding a simple system: Find all transpositions in $G$ and find the corresponding positive roots. Out of all these positive roots, find the unique minimal subset such that all positive roots are in the nonnegative span of the subset. The transpositions for that subset are the simple system.

In this case, $G$ will be a product of symmetric groups.