Enhancing the monoid structure over a finite alphabet to prove Arden's rule

Question

Suppose you have a finite-state, deterministic automaton, that you wish to convert to a regular expression. A common method, perhaps easier to apply by hand that Yamada's algorithm, is to reduce the automaton to a set of equalities between subsets of $A^*$, where $A$ is a finite alphabet (finite set), and $A^* = \bigcup_{n=0}^\infty A^n$.

A very useful lemma in solving these equations is Arden's rule, which states that the smallest subset $X \subset A^*$ satisfying the equation $X=K.X|L$ is $K^*L$, where $K, L \subset A^*$, $.$ denotes concatenation (product), and $|$ denotes a choice (union).

Now, consider the following, completely formal equalities:

$$ \begin{align} X &= KX+L\\ &= L + KX\\ X - KX &= L\\ (1-K)X &= L\\ X &= \frac1{1-K} L\\ &= \left(\sum_{n=0}^{\infty} K^n\right) L\\ &= K^*L \end{align} $$

Except for the first equality, all the other ones are based on undefined operations, but I've been wondering: since this type of calculations is valid in certain algebras, is there a way to define an algebraic structure over $A^*$ which would legitimate the previous calculations?

There might not be any, but I have the feeling that there's more to this than a mere coincidence.

Thanks for your ideas!

Answer 1

Your intuition is right. To make it formal, you have to work with rational series with noncommutative variables and coefficients in $\mathbf{Z}$. Here is a good reference on this topic:

J. Berstel and C. Reutenauer, Noncommutative rational series with applications. Encyclopedia of Mathematics and its Applications, 137. Cambridge University Press, Cambridge, 2011. xiv+248 pp. ISBN: 978-0-521-19022-0