The Question
Let $M$ be a finite monoid. Let $S$ be a generating set of $M$. Say we have a binary encoding of $S$ represented by $\phi:S \rightarrow A^*$ where $A = \{0, 1\}$. This encoding should have the prefix property.
There is a natural extension of $\phi$ to $M$; for any $a \in M$ choose $b_i \in S$ s.t. $b_1b_2 \cdots b_n = a$ and let $\phi(a) = \phi(b_1)\phi(b_2)\cdots\phi(b_n)$.
I would like to minimize the quantity $\sum_{a \in M} |\phi(a)|$ by choosing $S$ and $\phi$ intelligently. Is there a name for this problem? Has research been conducted on it?
Motivation
I am attempting to design an instruction set for a virtual machine which optimizes code density. In my specific case, $M$ is the transformation monoid on $X$ (e.g. the set of all mappings from $X$ to itself under composition) where $X$ represents the state-space for my machine. Alternately, $M$ can be thought of as the set of all programs my machine can execute and $S$ can be thought of as the instruction set. I assume someone has already thought long and hard about this question.
P.S.
For the sake of propriety, I will add that I have already asked a similar question on the Mathematics StackExchange. I feel that the original question was worded very poorly, and that the forum was inappropriate. Hopefully no one minds that I've asked an improved, slightly different question here. If there is a problem, I would be happy to delete the original question.
