# Finding generalised Lyndon words

Let $\Sigma = \lbrace a_1, \ldots, a_n, A_1, \ldots A_n \rbrace$ (where $A_i = a_i^{-1}$) and $\prec$ be a total ordering on $\Sigma$.

Let $\Sigma^*$ be the set of all words (generated by the alphabet $\Sigma$) and $\prec^*$ be the total ordering on $\Sigma^*$ induced by $\prec$ (dictionary / lexicographical ordering).

Let $G$ be a finitely presented group which acts on $\Sigma^*$.

For $w \in \Sigma^*$, let $[w]$ denote the equivalence class of words under $G$ (i.e. $[w] = \text{Orb}_G(w)$).

Let $\text{First}_G(w)$ be the first element of $[w]$ under the total ordering $\prec^*$ (i.e. $\text{First}_G(w)$ is the unique element of $[w]$ s.t. $\forall v \in [w] \backslash \lbrace \text{First}_G(w) \rbrace$, $\text{First}_G(w) \prec^* v$). The naive way to determine $\text{First}_G(w)$ is to first generate $[w]$ and then determine the 'first' element of this set, however in general $[w]$ may be an infinite set.

In the case when $G = \langle \Sigma^* | \rangle$ and $g \in G$ acts on $\Sigma^*$ by $g :w \mapsto gwg^{-1}$, $[w]$ is the set of cyclic permutations of $w$ and $\text{First}_G(w)$ is the unique Lyndon word in $[w]$. In this particular case, duval's algorithm will determine $\text{First}_G(w)$ without having to generate all of $[w]$.

Is there an algorithm for determining $\text{First}_G(w)$ without first determining all the elements of $[w]$ for a general group $G$ acting on $\Sigma^*$?

Or alternatively

Is there a $\Sigma$ and $G$ such that $\forall n$, $\exists w \in \Sigma^*$ such that there is no sequence $g_1, g_2, \ldots g_m \in G$ such that $(g_m \circ \cdots \circ g_1)(w) = \text{First}_G(w)$ and $\forall p < m$, $\text{length}((g_p \circ \cdots \circ g_1)(w)) - \text{length}(w) < n$?

i.e. For any bound $n$ there is a word $w$ that must be made more than $n$ letters longer during any sequence of group actions that take it to it's 'first' word.

-
You consider only reduced words? The action of $G$ on $F^*$ should preserve what? –  Mark Sapir Oct 2 '10 at 20:52