Here goes...
Let $n = 2^p$ for some $p \in \mathbb{N}$. Let $\mathcal{T}_n$ denote the set of all transformations on $\mathbb{Z}_n$ (viz. the transformation monoid).
Pick $C$ to be an order $|\mathcal{T}_n|$ subset of the set of all binary strings that has the prefix property. Let $\phi$ be a bijection from $C$ to $\mathcal{T}_n$ ($\phi$ gives us a unique encoding for each transformation).
Now define an equivalence relation $\sim$ on $C^*$ (where $C^*$ is the set of all words on $C$) s.t.
$$a_1a_2\cdots a_q\sim b_1b_2\cdots b_r$$
iff
$$\phi(a_1)\phi(a_2)\cdots\phi(a_q)=\phi(b_1)\phi(b_2)\cdots\phi(b_r).$$
We'll define the "optimal length" of $x \in C$ as $\|x\| = \min \{|a| : a \sim x\}$ (where $|a|$ denotes the length of $a$ on the set of binary strings). I am interested in the quantity $\lambda = \sum_{x \in C} \|x\|$. This naturally leads to several questions:
- How do I determine $\|x\|$?
- How do I choose $C$ and $\phi$ such that $\lambda$ is minimized?
- Is there a name for this problem and can anyone point me to any literature on it?
Thanks.
Update: I'm adding an example here to clarify what I'm attempting to communicate. Take $n = 2$. Then $\mathcal{T}_n = \{x, \neg x, T, F\}$. One choice for $C$ would be $\{(), (1), (01), (001)\}$. One choice for $\phi$ would be
$$\phi(()) = x$$ $$\phi((1)) = \neg x$$ $$\phi((01)) = T$$ $$\phi((0001)) = F$$
Then we have
$$\|\phi^{-1}(x)\| = \|()\| = 0,$$ $$\|\phi^{-1}(\neg x)\| = \|(1)\| = 1,$$ $$\|\phi^{-1}(T)\| = \|(01)\| = 2,$$
and because $(101) \sim (0001)$ (since $\phi((1))\phi((01)) = \neg T = F = \phi((0001))$)
$$\|\phi^{-1}(F)\| = \|0001\| = 3.$$
Therefore $\lambda = 6$, which I believe to be optimal for $n = 2$. (Before someone says something about $C$ not having the prefix property because the empty string is included, it is O.K. for my purposes in this instance specifically because it is mapped to the identity operator. Hopefully this is clear. Perhaps I should reword the bit about having the prefix property to include this.)
I still not fully understand your question, but here are some elements that may help you. First of all, for $n > 2$, you need at least three generators to generate $\mathcal{T_n}$. You could take for instance the following generators: \begin{align} a &= (2\ 3\ 4\ 5\ \dotsm \ n-1\ n\ 1) \quad \text{(a cyclic permutation)}\\ b &= (2\ 1\ 3\ 4\ \dotsm \ n-2\ n-1\ n) \quad \text{(the transposition exchanging $1$ and $2$)}\\ c &= (1\ 2\ 3\ 4\ \dotsm \ n-2\ n-1\ 1) \quad \text{(the identity on $\{1, \dotsm n-1\}$, but maps $n$ to $1$)} \end{align} Setting $A = \{a,b,c\}^*$, you now have a map $\varphi: A \to \mathcal{T_n}$, (defined, in the obvious way, by $\varphi(a) = a$, $\varphi(b) = b$, $\varphi(c) = c$). This map extends uniquely to a monoid morphism $\varphi: A^* \to \mathcal{T_n}$ by setting $$ \varphi(a_1a_2 \dotsm a_n) = \varphi(a_1) \varphi(a_2) \dotsm \varphi(a_n) $$ Now, you may look for a subset $C$ on $A^*$ such that $\varphi$ induces a bijection from $C$ onto $\mathcal{T_n}$, and you may look for an optimal such $C$, in the sense that the $\sum_{x \in C} |x|$ is minimal.
From a theoretical point of view, you just consider the Cayley graph of the $A$-generated monoid $\mathcal{T_n}$ and look for geodesics from $1$ to any element of $\mathcal{T_n}$.
From a practical point of view, you may use the C-program Semigroupe 2.01 which computes this for you (up to $n = 8$). The following LaTeX output was generated by this program \begin{align} &&1 &&2 &&3 \\ \hline 1 &&1 &&2 &&3 \\ a&&2 &&3 &&1 \\ b&&2 &&1 &&3 \\ c&&1 &&2 &&1 \\ aa&&3 &&1 &&2 \\ ab&&1 &&3 &&2 \\ ac&&2 &&1 &&1 \\ ba&&3 &&2 &&1 \\ ca&&2 &&3 &&2 \\ cb&&2 &&1 &&2 \\ aac&&1 &&1 &&2 \\ aca&&3 &&2 &&2 \\ acb&&1 &&2 &&2 \\ caa&&3 &&1 &&3 \\ cab&&1 &&3 &&1 \\ cba&&3 &&2 &&3 \\ aaca&&2 &&2 &&3 \\ aacb&&2 &&2 &&1 \\ acaa&&1 &&3 &&3 \\ acab&&3 &&1 &&1 \\ acba&&2 &&3 &&3 \\ caac&&1 &&1 &&1 \\ aacaa&&3 &&3 &&1 \\ aacab&&1 &&1 &&3 \\ aacba&&3 &&3 &&2 \\ caaca&&2 &&2 &&2 \\ caacaa&&3 &&3 &&3 \\ \hline \end{align} Relations \begin{align} bb &= 1 & bc &= ac & cc &= c & aaa &= 1 \\ aab &= ba & aba &= b & baa &= ab & bab &= aa \\ bac &= c & cac &= cb & acaac &= caac & caacb &= caaca \\ caacab &= caac \end{align}
Warning. The Cayley graph depends on the choice of the generators.