Given a finitely generated group $G$, define an *encoding* of $G$ to be a one-to-one function $\Phi:G\to \bigcup_n \{0,1\}^n$ that sends each group element to a unique finite word. For $a,b\in G$, assuming that $\Phi(ab)$ can be computed from $\Phi(a)$ and $\Phi(b)$, my question is: is there a classification for groups where there exists an encoding $\Phi$ such that $\Phi(e_ia)$ can be computed in *constant time* by a multi-tape Turing machine from $\Phi(e_i)$ and $\Phi(a)$ where $e_1,\ldots,e_n$ is some choice of generators and $a\in G$.

For example, $\mathbb Z$ has such an encoding. Expanding the encoding to allow strings with letters $\{0,1,*\}$, we can represent an element in $\mathbb Z$ as $\cdots 000*11\cdots 1\underline{1}000\cdots$ with the appropriate number of $1$s to the right or the left of $*$ for positive or negative values and $\underline{\phantom{a}}$ indicating the position of the head of the Turing machine. Then we just add or remove a $1$. Similarly, using multiple tapes, we can encode $\mathbb Z^n$. Using symbols $\{a,b,a^{-1},b^{-1}\}$ we can represent the free group on $\{a,b\}$ by just writing down its usual representation as words. We could also, for instance, encode the group $\langle a,b \mid aaa=e\rangle$. (For each of these examples, the head of the Turing machine should be left at the end of each encoding, otherwise the algorithm may not be constant time.) However, I'm not sure of more complicated examples.

I believe that operating on all encodings rather than directly on the encoding produced by representations in terms of generators makes this question distinct from ``groups where a multi-tape Turing machine can compute the application of a generator $e_i$ to a word $w=w_1\cdots w_n$ when given the input $\cdots 000.w_1\cdots w_n00\cdots$,'' but I don't have an example of a group where there exists a more computationally efficient encoding than just writing down the word in terms of generators.

I am also curious about the more general context of simultaneously constant-time operations on sets. For instance, on $\mathbb Z$, the function $f(x)=x+1$ can be accomplished in constant time by encoding $x$ as a string of $x$ $1$s. Similarly, the operation $g(x)=2x$ can be accomplished in constant time by encoding $x$ in binary. In binary $f(x)$ cannot be computed in constant time, and when written as $x$ $1$s, $g(x)$ cannot be computed in constant time. Does there exist an encoding of $\mathbb Z$ such that both $f$ and $g$ can be computed in constant time? Is there a name for such collections of operations?