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 welldefined. Furthermore, under $\varphi $, it is easy to see that $C(M)$ is antiisomorphic to ${\mathrm{\Sigma}}^{*}/\sim $.
Remark. In order to avoid using antiisomorphisms, 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)$.
References
 1 A. Ginzburg, Algebraic Theory of Automata, Academic Press (1968).
 2 M. Ito, Algebraic Theory of Automata and Languages^{}, World Scientific, Singapore (2004).
Title  characteristic monoid 

Canonical name  CharacteristicMonoid 
Date of creation  20130322 19:01:10 
Last modified on  20130322 19:01:10 
Owner  CWoo (3771) 
Last modified by  CWoo (3771) 
Numerical id  8 
Author  CWoo (3771) 
Entry type  Definition 
Classification  msc 68Q70 
Classification  msc 20M35 
Classification  msc 03D05 
Classification  msc 68Q45 