# Represent an element in a free monoid with minimum weight

Consider a rank $k$ free monoid $(M,⋅)$ 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}$.

Find the shortest way to write down an element in a free monoid.

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_{∗},⋅)$,

- $a∈G⟹Atom(a)∈M_{∗}$.
- $a∈M_{∗}$, $n∈N$, then $Power(a,n)∈M_{∗}$.

Consider a homomorphism $w:M_{∗}→N$. Such that for all $n$, it satisfy the following criteria:

- $w(a)≤w(b)⟹w(Power(a,n))≤w(Power(b,n))$,
- $w(a)≤w(Power(a,1))$.

$w$ is a weight function.

Let $f:M_{∗}→M$, such that

- $f(ab)=f(a)f(b)$,
- $f(Atom(a))=a$,
- $f(Power(a,n))=a_{n}$.

Given $a∈M$, we want to find $a_{′}∈M_{∗}$, such that $f(a_{′})=a$ and $w(a_{′})$ is minimized.

The input is $a_{1}…a_{n}$.

Let $D(i,j)$ represent the minimum weight representation for $a_{i}…a_{j}$. Let $P(i,j)$ represent the set of all possible $Power(x,k)$, such that $f(Power(x,k))=a_{i}…a_{j}$ for some $k=1$.

$D(i,i)D(i,j) =a_{i}=min(P(i,j)∪{D(i,k)+D(k+1,j)∣i≤k≤j−1}) $

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.