4
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ You consider only reduced words? The action of $G$ on $F^*$ should preserve what? $\endgroup$ – Mark Sapir Oct 2 '10 at 20:52
  • $\begingroup$ can you please explain, why is [w] is the set of all cyclic permutations of w ? I can see only one side inclusion. $\endgroup$ – GA316 Apr 15 '16 at 5:29

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.