Please see my update here, that's more complicated than I thought.

This reminds me of what my prof called a "Minimales Wort Problem" in my studies, but I couldn't find a link for it.

Basically finding the shortest algebraic term expressing a solution, the {,a,b} clauses are operations here.

Problem now is that I doubt that there is always a unique minimal solution, which can be reached by a path of successive optimization steps.

This means you have to try different steps in different order, which will indeed explode the complexity.