Not many results in Computer Science are recognised to be as basic and fundamental as Kleene Theorem. It states the equality of two sets of objects that we call now languages. A slight change of focus on this result shows how it is essentially the combination of two families of algorithms: algorithms that transform a finite automaton into a regular expression on one hand and algorithms that build a finite automaton from a regular expression on the other.
In this talk, I shall consider the algorithms of the latter family, a much laboured subject of both theoretical and practical interests. I shall present three different constructions, classically attributed to Thompson, Glushkov, and Brzozowski-Antimirov respectively, and their relationships.
We shall then see how the extension of Kleene Theorem beyond languages: to subsets of arbitrary monoids first and second to subsets with multiplicity, leads to a modification of the construction for the first one and to a radical transformation of the proof for the third.
All recent results were obtained in joint works with Sylvain Lombardy.
