Represent an element in a free monoid with minimum weight

Consider a rank $k$ free monoid $(M,\cdot )$ with free generators $G$. Sometimes there are ways to express them by writing a little less than write the whole string of generators. We can group some generators by powers. For example, $aababababaaaa=a(ab{)}^4{a}^4$.

There are problems on how long are the parentheses, exponents etc. Therefore we generalize it to allow weight to those operations.

Formally. For any free monoid $M$ with free generators $G$, we can construct another free monoid $(M^{\ast },\cdot )$,

1. $a\in G⟹Atom(a)\in M^{\ast }$.
2. $a\in M^{\ast }$, $n\in \mathbb{N}$, then $Power(a,n)\in M^{\ast }$.

Let $f:M^{\ast }\to M$, such that

• $f(ab)=f(a)f(b)$,
• $f(Atom(a))=a$,
• $f(Power(a,n))=a^n$.

The input is $a_1\dots a_n$.

Let $D(i,j)$ represent the minimum weight representation for $a_i\dots a_j$. Let $P(i,j)$ represent the set of all possible $Power(x,k)$, such that $f(Power(x,k))=a_i\dots a_j$ for some $k\ne 1$.

$$\begin{array}{rl}D(i,i)& =a_i\\ D(i,j)& =\min (P(i,j)\cup \{D(i,k)+D(k+1,j)|i\le k\le j-1\})\end{array}$$

Here $\min$ return any of the expressions that achieves the minimum weight. This allows a $O(n^3)$ algorithm if one uses suffix tree for finding $P(i,j)$. One can naively try all possible $Power(x,k)$ instead, where $k|n$.

Here is an Haskell code for it. It is designed to show the algorithm instead of been efficient. This has real life usage to compress regular expressions.