Words of the Normal Form of the Presentation of a Finite Monoid

Question

Massive Edit:

After consulting with a few mathematicians at my university, I got a better understanding of what I was actually looking for.

$$ \langle\ s,\ t\ \vert\ s^2 = 1,\ t^n = 1\ \rangle $$

This is the presentation of a monoid $M_n$ which generalizes the symmetric group $S_n$. For my needs, it's important that the words in the presentation do not contain inverses or negative powers.

Specifically, the generators $s$ and $t$ are the following cycles:

$$ s = (1\ \ n) \\ t = (1\ \ 2\ \ 3\ \ \dots\ \ n) $$

The normal form of that presentation for $M_3$ is easy to enumerate.

$$ 1, s, t, st, ts, tt $$

My Question (Restated)

Given an element $m$ of $M_n$, is there a fast procedure $P$ to find the word $w$ in the normal form of the presentation of $M_n$ that corresponds to $m$?

I want a general answer that applies to arbitrary large $n$.

For example, in $M_3$, if I have the element $m = (2,\ 1,\ 3)$, I want to get $w = ts$ without having to enumerate the entire normal form of the presentation of $M_3$.

My Attempt

$P(m) = P(m,\ 1,\ \varepsilon,\ \{1 \to 1\},\ 0)$

procedure P(m, m_0, w, D, s_?):
    if (w not equal shortest(D(m_0), w)):
        return null
    D = set(D, m_0 -> w)
    if (m equals m_0):
        return w
    if (s_? equals 0):
        return shortest(P(m, m_0 * t, w || t, D, 0), 
                        P(m, m_0 * s, w || s, D, 1))
    if (s_? equals 1):
        return P(m, m_0 * t, w || t, D, 0)

$\text{shortest}(w_1, w_2) = \begin{cases} w_1 & \mbox{if} \quad \ w_2 \ = \ \ \varnothing \\ w_2 & \mbox{if} \quad \ w_1 \ = \ \ \varnothing \\ w_1 & \mbox{if} \quad |w_1| \le |w_2| \\ w_2 & \mbox{if} \quad |w_2| < |w_1| \end{cases}$

$\text{set}(D,\ m \to w) = \{m \to w\} \cup (D \setminus \{m \to y\ |\ (m \to y) \in D \})$
Essentially, this function treats $D$ as a dictionary and sets the value at $m$ to $w$.

$||$ is the concatenation operator.

The procedure $P$ above is a tree-search through all combinations until it hits words that represent the element $m$, and then the tree will be bound by at-most enumerating the entire presentation. This procedure is the most efficient one I could think of, but I'd like a faster one. It's limited by time and space, so for arbitrarily large $n$, it's not possible to follow this procedure.

Is there a faster procedure that works for arbitrarily large $n$?

Answer 1

What you need to know is the relations between $s_n$ and $t_n$. This amounts to knowing the relations in the presentation $$\langle s_n, t_n\ |\ \text{some relations}\rangle.$$ The set of relations is not simple or short. See here for one discussion.