Represent an element in a free monoid with minimum weight
Consider a rank free monoid with free generators . 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, .
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 with free generators , we can construct another free monoid ,
- , , then .
Consider a homomorphism . Such that for all , it satisfy the following criteria:
is a weight function.
Let , such that
Given , we want to find , such that and is minimized.
The input is .
Let represent the minimum weight representation for . Let represent the set of all possible , such that for some .
Here return any of the expressions that achieves the minimum weight. This allows a algorithm if one uses suffix tree for finding . One can naively try all possible instead, where .
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.