In 1978, Courcelle showed that (initial) solutions certain systems of finite fixed point equations in words could be expressed by regular expressions formed from letters in a fixed alphabet using word operations of concatenation (or product), omega and omega-op power.

For example, the initial solution to the equation (1) is written (a.b)^omega.

Courcelle asked for a complete equational axiomatization of words with product, omega and omega-op power.

In 1981, Heilbrunner showed that all systems of finite fixed point equations in words could be expressed using the operations above together with infinitely many 'shuffle operations'. He asked for a complete equational axiomatization of words with all of these operations.

A 'regular expression' on the alphabet A is a term formed from letters in A using the operations of composition, omega, omega-op power and the shuffle operations.

In 1986, Thomas found an algorithm to decide when $|s|=|t|$, for regular expressions $s,t,$, where $|s|$ is the word named by the expression $s$. Thomas' algorithm requires $O(2^{2^n})$-steps, where $n$ is the total number of symbols in $s,t$.

In 2001, Bloom and Choffrut gave a complete equational axiomatization for product and omega power.

In 2002, Bloom and \'Esik found a complete equational axiomatization for product, omega and omega-op power.

The talk will describe the complete solution to Heilbrunner's question and a polynomial time algorithm to decide if $|s|=|t|$.