You are here
Homecharacteristic monoid
Primary tabs
characteristic monoid
Given a semiautomaton $M=(S,\Sigma,\delta)$, the transition function is typically defined as a function from $S\times\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\Sigma\},\qquad\mbox{where}\qquad\delta_{a}(% s):=\delta(s,a).$ 
Since the transition function $\delta$ in $M$ can be extended to the domain $S\times\Sigma^{*}$, so can the set $C(M)$:
$C(M):=\{\delta_{u}:S\to S\mid u\in\Sigma^{*}\},\qquad\mbox{where}\qquad\delta_% {u}(s):=\delta(s,u).$ 
The advantage of this interpreation is the following: for any input words $u,v$ over $\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 $\Sigma^{*}$ generated by $\Sigma$ in the following manner: define a binary relation $\sim$ on $\Sigma^{*}$ by $u\sim v$ iff $\delta_{u}=\delta_{v}$. Then $\sim$ is clearly an equivalence relation on $\Sigma^{*}$. It is also a congruence relation with respect to concatenation: if $u\sim v$, then for any $w$ over $\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 $\Sigma^{*}/\sim$ containing the word $u$.
Now, define a map $\phi:C(M)\to\Sigma^{*}/\sim$ by setting $\phi(\delta_{u})=[u]$. Then $\phi$ is welldefined. Furthermore, under $\phi$, it is easy to see that $C(M)$ is antiisomorphic to $\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 $\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).
Mathematics Subject Classification
68Q70 no label found20M35 no label found03D05 no label found68Q45 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
 Corrections