# 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 well-defined. Furthermore, under $\phi$, it is easy to see that $C(M)$ is anti-isomorphic to $\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 $\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 CharacteristicMonoid 2013-03-22 19:01:10 2013-03-22 19:01:10 CWoo (3771) CWoo (3771) 8 CWoo (3771) Definition msc 68Q70 msc 20M35 msc 03D05 msc 68Q45