Two conjectures of Conway on rational expressions of languages are proved: the two following systems of identities are complete systems of identities (i.e. each rational identity is a consequence of the system):

1. The identities $\left(M\right)$, $\left(S\right)$ and $P\left(M\right)$ for each finite monoid $M$.

2. The identities $\left(M\right)$, $\left(S\right)$ and $P\left(G\right)$ for each finite group $G$.

There special identities are: $\left(M\right)$ ${\left(ab\right)}^{*}=1+a{\left(ba\right)}^{*}b$; $\left(S\right)$ ${(a+b)}^{*}={\left({a}^{*}b\right)}^{*}{a}^{*}$; $P\left(M\right)$ ${A}_{M}^{*}={\sum}_{m\in M}{\varphi}_{M}^{-1}\left(m\right)$, where ${A}_{M}$ is an alphabet in bijection with $M$, ${\varphi}_{M}:{A}_{M}^{*}\to M$ the natural monoid homomorphism, and ${\varphi}_{M}^{-1}\left(m\right)$ represents a rational expression naturally associated to this language.

The considerable work done by the author in order to solve these conjectures has many byproducts: completeness of certain meta-rule systems; characterization fo aperiodic semigroups by deductibility of their rational expression from $\left(M\right)$ and $\left(S\right)$; formal proof of Schützenberger’s star-free theorem; deduction of the matrix semigroup identity from the semigroup identity; stability of identities under operations (subsemigroup, quotient, semidirect product), which allows to use the theorem of Krohn-Rhodes; completeness of $\left(M\right)$, $\left(S\right)$ together with the symmetric group identities.

##### MSC:

68Q45 | Formal languages and automata |