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?


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.


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.

  • $\begingroup$ Since your monoid is finite, this seems like a variant of Huffman coding. Write down the representation of each element of M in terms of S, look at the frequency with which each element of S shows up, build a Huffman code from that frequency list, and then use that to encode the elements of S. I just realized that you also need to choose S, but this is a way to optimize phi for any fixed S. $\endgroup$ – Suresh Venkat Jul 23 '15 at 7:05
  • $\begingroup$ It seems to be trickier than that, since if $M$ is non-free, its elements need not have a unique representation, i.e. you are looking for both an encoding of $S$ and a choice of representation. $\endgroup$ – Klaus Draeger Jul 23 '15 at 9:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.