characteristic monoid

Given a semiautomaton $M=(S,\mathrm{\Sigma },\delta )$, the transition function is typically defined as a function from $S\times \mathrm{\Sigma }$ to $S$. One may instead think of $\delta$ as a set $C(M)$ of functions

$$C(M):=\{{\delta }_a:S\to S\mid a\in \mathrm{\Sigma }\},\text{where}\mathit{\hspace{1em}\hspace{1em}}{\delta }_a(s):=\delta (s,a).$$

Since the transition function $\delta$ in $M$ can be extended to the domain $S\times {\mathrm{\Sigma }}^{*}$, so can the set $C(M)$:

$$C(M):=\{{\delta }_u:S\to S\mid u\in {\mathrm{\Sigma }}^{*}\},\text{where}\mathit{\hspace{1em}\hspace{1em}}{\delta }_u(s):=\delta (s,u).$$

The advantage of this interpreation is the following: for any input words $u,v$ over $\mathrm{\Sigma }$:

$${\delta }_u\circ {\delta }_v={\delta }_{vu},$$

which can be easily verified:

$${\delta }_{vu}(s)=\delta (s,vu)=\delta (\delta (s,v),u)=\delta ({\delta }_v(s),u)={\delta }_u({\delta }_v(s))=({\delta }_u\circ {\delta }_v)(s).$$

In particular, ${\delta }_{\lambda }$ is the identity function on $S$, so that the set $C(M)$ becomes a monoid, called the characteristic monoid of $M$.

The characteristic monoid $C(M)$ of a semiautomaton $M$ is related to the free monoid ${\mathrm{\Sigma }}^{*}$ generated by $\mathrm{\Sigma }$ in the following manner: define a binary relation $\sim$ on ${\mathrm{\Sigma }}^{*}$ by $u\sim v$ iff ${\delta }_u={\delta }_v$. Then $\sim$ is clearly an equivalence relation on ${\mathrm{\Sigma }}^{*}$. It is also a congruence relation with respect to concatenation: if $u\sim v$, then for any $w$ over $\mathrm{\Sigma }$:

$${\delta }_{uw}(s)={\delta }_u({\delta }_w(s))={\delta }_v({\delta }_w(s))={\delta }_{vw}(s)$$

and

$${\delta }_{wu}(s)={\delta }_w({\delta }_u(s))={\delta }_w({\delta }_v(s))={\delta }_{wv}(s).$$

Putting the two together, we see that if $x\sim y$, then $ux\sim vx\sim vy$. We denote $[u]$ the congruence class in ${\mathrm{\Sigma }}^{*}/\sim$ containing the word $u$.

Now, define a map $\varphi :C(M)\to {\mathrm{\Sigma }}^{*}/\sim$ by setting $\varphi ({\delta }_u)=[u]$. Then $\varphi$ is well-defined. Furthermore, under $\varphi$, it is easy to see that $C(M)$ is anti-isomorphic to ${\mathrm{\Sigma }}^{*}/\sim$.

Remark. In order to avoid using anti-isomorphisms, the usual practice is to introduce a multiplication $\cdot$ on $C(M)$ so that ${\delta }_u\cdot {\delta }_v:={\delta }_v\circ {\delta }_u$. Then $C(M)$ under $\cdot$ is isomorphic to ${\mathrm{\Sigma }}^{*}/\sim$.

Some properties:

• If $M$ and $N$ are isomorphic semiautomata with identical input alphabet, then $C(M)=C(N)$.

• If $N$ is a subsemiautomaton of $M$, then $C(N)$ is a homomorphic image of a submonoid of $C(M)$.

• If $N$ is a homomorphic image of $M$, so is $C(N)$ a homomorphic image of $C(M)$.